官方题解

题目大意

给定一个只包含数字的字符串，找出这个字符串重新排列组合后，能组成多少种不同的平方数。

解题思路

一个 $13$ 位数字，最大为 $9999999999999$ ，打表发现 $10^{14}$ 以内的平方数有 $3162278$ 个。

所以我们可以先预处理出 $10^{14}$ 以内所有的平方数，再对这些平方数逐一检查是否可以被给定字符串组成。

在检查时，我们只需要判断 $1$ ~ $9$ 的数字个数是否完全相等，并且给定字符串 $0$ 的个数要大于等于平方数的 $0$ 的个数。

参考答案

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 1e9+10;
const int N = 1000010;

vector<ll>st;

void init(){
    for(ll i=0;i*i<=10000000000000;i++){
        st.push_back(i*i);
    }
}

int cnt[10];
int cnt2[10];

int main(){
    init();
    int n;cin>>n;
    string s;cin>>s;
    for(auto c:s){
        ll x=c-'0';
        cnt[x]++;
    }

    ll res=0;
    for(auto c:st){
        for(int i=0;i<10;i++) cnt2[i]=0;

        ll x=c;
        if(x==0) cnt2[0]++;
        while(x){
            cnt2[x%10]++;
            x/=10;
        }
        
        if(cnt[0]<cnt2[0]) continue;

        int flag=0;
        for(int i=1;i<10;i++){
            if(cnt[i]!=cnt2[i]){
                flag=1;
                break;
            }
        }
        if(!flag) res++;
    }
    cout<<res<<endl;
    return 0;
}