平方数 \(X\) が長さ \(N\) の文字列 \(S\) を並べ替えたものならば、\(X\) は \(10 ^ N\) 未満の平方数である必要があります。

\(10 ^ N\) 未満の平方数はたかだか \(\left\lfloor\sqrt{10 ^ N}\right\rfloor\) 個です。 これらの平方数すべてについて、\(S\) を並べ替えてその数にできるかを判定すればよいです。

次の問題を考えます。

\(2\) つの文字列 \(S,T\) がある。一方を並べ替えてもう一方と等しくできるか判定してください。

どの文字 \(c\) についても、 \(S\) に \(c\) が含まれる個数 \(=T\) に \(c\) が含まれる個数 が成り立つことが必要十分条件です。

実際に 0, 1, …, 9 について個数を数えることや、\(S,T\) をソートした結果が等しいか判定することでこの条件をチェックすることができます。

実装例は以下のようになります。 時間計算量は \(O(N10 ^ {N/2})\) や \(O(N10 ^ {N/2}\log N)\) などになります。

#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

int main() {
    using namespace std;

    int N;
    string S;
    cin >> N >> S;

    ranges::sort(S); // S をソートしておく

    long max_value = pow(10, N);

    int ans = 0;
    for (long i = 0; i * i < max_value; ++i) {
        string T = to_string(i * i);
        T.resize(N, '0'); // 桁数を揃える
        ranges::sort(T); // ソートして
        if (S == T)
            ++ans; // 一致するか判定
    }
    cout << ans << endl;

    return 0;
}