If a square number \(X\) is a permutation of a string \(S\) of length \(N\), then \(X\) must be a square number less than \(10 ^ N\).

There are at most \(\left\lfloor\sqrt{10 ^ N}\right\rfloor\) square numbers less \(10 ^ N\). It is sufficient to check if each of them can be obtained as a permutation of \(S\).

Consider the following question.

Given two strings \(S\) and \(T\), determine if one can rearrange the former to obtain the latter.

It is true if and only if \(S\) and \(T\) contains the same number of \(c\) for all characters \(c\).

The condition can be checked by counting the number of occurrences of 0, 1, …, and 9, or by sorting \(S\) and \(T\) to see if they fall into the same strings.

The following is sample code. The time complexity is about \(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); // Sort S beforehand

    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'); // Let T have the same number of digits as S
        ranges::sort(T); // Sort T
        if (S == T)
            ++ans; // Determine if they coincide
    }
    cout << ans << endl;

    return 0;
}