AT_abc324_d [ABC324D] Square Permutation

题目描述

给定一个仅由数字组成、长度为 $N$ 的字符串 $S$。

请计算，将 $S$ 的各位数字重新排列后，能组成多少个十进制整数，使得这些整数是完全平方数。

更严格地说，定义 $S$ 的第 $i$ 位数字为 $s_i$（$1\leq i\leq N$）。

对于 $(1,\ldots,N)$ 的任意一个排列 $P=(p_1,p_2,\ldots,p_N)$，可以表示出一个整数 $\displaystyle\sum_{i=1}^N s_{p_i}10^{N-i}$。请计算，在所有可能的排列中，有多少个不同的整数是完全平方数。

输入格式

输入从标准输入中给出，格式如下：

$N$ $S$

输出格式

请输出一个整数，表示满足条件的不同完全平方数的个数。

输入输出样例 #1

输入 #1

4
4320

输出 #1

2

输入输出样例 #2

输入 #2

3
010

输出 #2

2

输入输出样例 #3

输入 #3

13
8694027811503

输出 #3

840

说明/提示

限制条件

• $1\leq N\leq 13$
• $S$ 是长度为 $N$ 的仅由数字组成的字符串
• $N$ 是整数

样例解释 1

当 $P=(4,2,3,1)$ 时，有 $s_4\times10^3+s_2\times10^2+s_3\times10^1+s_1=324=18^2$。
当 $P=(3,2,4,1)$ 时，有 $s_3\times10^3+s_2\times10^2+s_4\times10^1+s_1=2304=48^2$。
除此之外，没有其他排列能得到完全平方数，因此输出 $2$。

样例解释 2

当 $P=(1,3,2)$ 或 $P=(3,1,2)$ 时，有 $\displaystyle\sum_{i=1}^N s_{p_i}10^{N-i}=1=1^2$。
当 $P=(2,1,3)$ 或 $P=(2,3,1)$ 时，有 $\displaystyle\sum_{i=1}^N s_{p_i}10^{N-i}=100=10^2$。
除此之外，没有其他排列能得到完全平方数，因此输出 $2$。
请注意，如果不同的排列得到相同的数，只计为 $1$ 个。

由 ChatGPT 4.1 翻译