分数: 425 点
问题陈述
给你一个字符串 S 长度 N 由数字组成。
找出可以通过解释排列获得的平方数的数量 S 作为十进制整数。
更正式地解决以下问题。
让 s _ i 是对应的数字 i第一位数字 (1\leq i\leq N) 从开始 S.
找出可以表示为的平方数的个数 \displaystyle \sum _ {i=1} ^ N s _ {p _ i}10 ^ {N-i} 具有排列 P=(p _ 1,p _ 2,\ldots,p _ N) of (1, \dots, N).
约束
- 1\leq N\leq 13
- S 是一个长度为的字符串 N 由数字组成。
- N 是一个整数。
输入
输入由标准输入按以下格式给出:
N S
输出
在一行中打印答案。
示例输入 1
4 4320
示例输出 1
2
对于 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
3 010
示例输出 2
2
对于 P=(1,3,2) or P=(3,1,2),我们有 \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=1=1 ^ 2.
对于 P=(2,1,3) or P=(2,3,1),我们有 \displaystyle\sum _ {i=1} ^ Ns _ {p _ i}10 ^ {N-i}=100=10 ^ 2.
没有其他排列会产生平方数,因此您应该打印 2。 请注意,如果不同的排列产生相同的数字,则无法区分它们。
示例输入 3
13 8694027811503
示例输出 3
840