解法
\(N \leq 13\) より,\(N\)桁の平方数は \(10^{6.5}\) 以下なので,全探索できる.
\(0\)の桁の扱いに注意. 一番上の桁に\(0\)を追加してもよいという設定.
あるソートで一致することは, 各桁の\(0\)から\(9\)の個数が全て一致することと同値. これは,個数を格納した配列をソートして一致するかで判定できる.
使っている記号,マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n;
cin >> n;
string s; cin >> s;
sort(all(s));
vll sq;
{
ll i = 0;
ll pow = 1; rep(_,s.length()) pow *= 10;
while(i*i < pow) {sq.push_back(i*i); i++ ;}
}
ll ans = 0;
for(auto i:sq){
string t;
ll ni = i; while(ni) {
t.push_back(ni%10 + '0');
ni/=10;
}
while(t.size() < s.size()) t.push_back('0');
sort(all(t));
if(t == s) ans++;
}
cout << ans << endl;
return 0;
}