← 返回题目列表

AtCoder · abc324_d

G. 平方排列

中文机器翻译题面 查看原题

分数: 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