题目解析
涂黑的一组方格与棋子移动的方法相关，因此只需计算到达每个方格的方案数即可。
若我们忽略解法的复杂度我们可以使用以下这种动态规划的方法来解决这个问题：
当 AiA_iAi 较大时，对 jjj 的迭代不会重复很多次，所以这种方法似乎是合理的，但如果以 Ai=[1,1,…,1]A_i=[1,1,\dots,1]Ai =[1,1,…,1] 为例，则需要花费 O(N2)O(N^2)O(N2) 的时间，所以这种算法无法通过本题。
考虑在 AiA_iAi 相同的情况下集体更新。具体来说，在从 iii 开始的转换过程中，如果存在 jjj 使得 Ai=AjA_i=A_jAi =Aj ，那么之后在 jjj 的循环过程中将它们全部相加。
时间复杂度
上述方法可以在 O(NN)O(N\sqrt N)O(NN ) 的时间复杂度内完成。
如果每个 AiA_iAi 在更新的过程中全部重复掉，那么对于每个 AiA_iAi 只需要将其移动一次，之后让 AjA_jAj 代替 AiA_iAi 更新。
最坏的情况是没有 "一起更新"，并且 AiA_iAi 的值尽可能的小。
在这种情况下，AAA 就像这个样子 [1,2,2,3,3,3,4,⋯ ][1, 2, 2, 3, 3, 3, 4, \cdots][1,2,2,3,3,3,4,⋯]，而那么 jjj 的调用次数为：
N1+N2+N2+N3+N3+N3+N4+⋯\frac{N}{1} + \frac{N}{2} + \frac{N}{2} + \frac{N}{3} + \frac{N}{3} + \frac{N}{3} + \frac{N}{4} + \cdots 1N +2N +2N +3N +3N +3N +4N +⋯
即：
N×(1+2×12+3×13+4×14+⋯+M×1M+⋯)N \times \big(1 + 2 \times \frac{1}{2} + 3 \times \frac{1}{3} + 4 \times \frac{1}{4} + \cdots + M \times \frac{1}{M} + \cdots\big) N×(1+2×21 +3×31 +4×41 +⋯+M×M1 +⋯)
上式中 1+2+3+4+⋯+M=M×(M+1)2=N1 + 2 + 3 + 4 + \cdots + M = \frac{M \times (M + 1)}{2} = N1+2+3+4+⋯+M=2M×(M+1) =N 所以 O(M)=O(N)O(M) = O(\sqrt{N})O(M)=O(N )
那么我们可以由上式得到：
O(N×(1+1+1+⋯+1⏞M+⋯))=O(NN)O \big(N \times \big( \overbrace{1 + 1 + 1 + \cdots + 1}^{M} + \cdots\big)\big) = O(N\sqrt{N}) O(N×(1+1+1+⋯+1 M +⋯))=O(NN )
故整体算法时间复杂度为 O(NN)O(N\sqrt{N})O(NN )。
AC代码
