⇒ \Rightarrow ⇒原题链接

可以发现行数和列数相当小，可以将其中一维状压，同时因为奇数步和偶数步的操作很类似，只需要考虑其中一种就行了，这里考虑奇数步。

设 f ( S ) f(S) f(S) 表示当前位置所在的行的集合为 S S S 的方案数，接下来我们需要计算出 g ( S ) g(S) g(S) ，其意义是所在的列的集合为 S S S 的方案数，这时候我们从 f ( S ) f(S) f(S) 中找一个数字 a a a 拓展，其能到达的行的集合为 D ( S , a ) D(S,a) D(S,a) ，那么可以得到转移： g ( D ( S , a ) ) ← f ( S ) g(D(S,a))\leftarrow f(S) g(D(S,a))←f(S)

这个 D ( S , a ) D(S,a) D(S,a) 可以使用 D ( S , a ) = { j ∣ i ∈ S , a i , j = a } D(S,a)=\{j\mid i\in S, a_{i,j}=a\} D(S,a)={j∣i∈S,ai,j​=a} 得到。

初始条件显然是 f ( { 1 , 2 , 3 , … , h } ) = 1 f(\{1,2,3,\dots, h\}) = 1 f({1,2,3,…,h})=1

⇒ \Rightarrow ⇒原题链接

容易想到二分，然后 check \verb|check| check 的时候显然要选择编号连续的一段，保持中间的不动，然后两头往中间靠就行了。

⇒ \Rightarrow ⇒原题链接

可以先写一下题目要求的式子： A N S = ∑ i = 1 n ∑ j = i n [ ( i , j ) > 1 ∧ ( p i , p j ) > 1 ] \mathrm{ANS}= \sum_{i=1}^n \sum_{j=i}^n \left[(i,j)> 1 \land \left(p_i,p_j\right)> 1\right] ANS=i=1∑n​j=i∑n​[(i,j)>1∧(pi​,pj​)>1]

对于形如 [ n > 1 ] [n>1] [n>1] 的判断式，可以使用莫比乌斯函数的性质： ∑ d ∣ n μ ~ ( d ) = [ n > 1 ] \sum_{d|n} \tilde\mu(d)=[n>1] ∑d∣n​μ~​(d)=[n>1] 展开。注意，这个 μ ~ ( n ) = − μ ( n ) \tilde\mu(n)=-\mu(n) μ~​(n)=−μ(n) 。由于原题的条件式是 and \verb|and| and ，因此可以直接将两个求和乘起来。

变化一下： A N S = ∑ i = 1 n ∑ j = i n ∑ d ∣ ( i , j ) ∑ g ∣ ( p i , p j ) μ ~ ( d ) μ ~ ( g ) \mathrm{ANS}= \sum_{i=1}^n \sum_{j=i}^n \sum_{d|(i,j)} \sum_{g|\left(p_i,p_j\right)} \tilde\mu(d) \tilde\mu(g) ANS=i=1∑n​j=i∑n​d∣(i,j)∑​g∣(pi​,pj​)∑​μ~​(d)μ~​(g)

按照化式子的套路，可以将 d , g d,g d,g 放到前面去： A N S = ∑ d = 1 n ∑ g = 1 n μ ~ ( d ) μ ~ ( g ) ∑ i = 1 n ∑ j = i n [ d ∣ i   ∧   d ∣ j   ∧   g ∣ p i   ∧   g ∣ p j ] \mathrm{ANS}= \sum_{d=1}^n \sum_{g=1}^n \tilde\mu(d) \tilde\mu(g) \sum_{i=1}^n \sum_{j=i}^n [d|i~\land~d|j~\land~g|p_i~\land~g|p_j] ANS=d=1∑n​g=1∑n​μ~​(d)μ~​(g)i=1∑n​j=i∑n​[d∣i ∧ d∣j ∧ g∣pi​ ∧ g∣pj​]

后面两个 Σ \Sigma Σ 可以看成是一个关于 d , g d,g d,g 的函数，但是因为 d , g d,g d,g 对 i , j i,j i,j 的限制其实是一样的，因此设 f ( d , g ) = ∑ i = 1 n [ d ∣ i   ∧   g ∣ p i ] f(d,g)=\sum_{i=1}^n [d|i~\land~g|p_i] f(d,g)=∑i=1n​[d∣i ∧ g∣pi​] ，那么式子就变成了： A N S = ∑ d = 1 n ∑ g = 1 n μ ~ ( d ) μ ~ ( g ) f ( d , g ) [ f ( d , g ) + 1 ] 2 \mathrm{ANS}=\sum_{d=1}^n \sum_{g=1}^n \tilde\mu(d) \tilde\mu(g) \frac{f(d,g)[f(d,g)+1]}{2} ANS=d=1∑n​g=1∑n​μ~​(d)μ~​(g)2f(d,g)[f(d,g)+1]​

μ ~ ( n ) ≠ 0 \tilde\mu(n)\ne 0 μ~​(n)​=0 位置不多，将这些位置都找出来。

⇒ \Rightarrow ⇒原题链接

写了一堆假做法。

首先将字符串排序，使其满足对于任意一组 1 ≤ i < j ≤ N 1\leq i < j\leq N 1≤i