Square Permutation

题目描述

给你一个长度为 $N$ 的由数字组成的字符串 $S$。 通过将 $S$ 的一个排列解释为十进制整数，求可以得到的平方数的个数。 更正式地，求解以下问题。 设 $s_i$ 为字符串 $S$ 从前往后第 $i$ 位对应的数字 $(1\leq i\leq N)$。 求可以表示为 $\displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i}$ 的平方数的个数，这里 $P=(p _ 1,p _ 2,\ldots,p _ N)$ 是 $(1,\dots,N)$ 的一个排列。

输入格式

输入由标准输入按以下格式给出： $N$ $S$

输出格式

在一行中输出答案。

4
4320

2

3
010

2

13
8694027811503

840

提示

$1\leq N\leq 13$ $S$ 是长度为 $N$ 的由数字组成的字符串。 $N$ 是一个整数。对于 $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$.
对于 $P=(1,3,2)$ 或 $P=(3,1,2)$，有 $\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2$.
对于 $P=(2,1,3)$ 或 $P=(2,3,1)$，有 $\displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2$。 没有其他排列会得到平方数，所以应该输出 $2$。 注意，如果不同排列得到相同的数字则不区分它们。

标签: AtCoder|abc324D

来源

AtCoder|abc324D