题解：P17351 [ECNA 2025] Polyomino Tiling

· · 题解

题意简述

给定多连块的边界方向串，方向分别为上、右、下、左。记 \overline{X} 为将字符串 X 翻转，并把每个方向替换为反方向后得到的字符串。

对边界串的每个循环移位，统计将它写成 XY\overline{X}\overline{Y} 或 XYZ\overline{X}\overline{Y}\overline{Z} 的方案数，其中所有块均非空，求这些方案数的总和。

解题思路

设边界串长度为 n。闭合路径的上下步数相等、左右步数相等，因此 n 为偶数。记 h=n/2。

固定一个循环起点，将对应字符串的前后两半记为 U,V，长度都为 h。在两种目标形式中，前一半和后一半的分界一定在位置 h，因为每一块与其反向取反串等长。

因此，需要把 U,V 在相同位置切成两段或三段，并要求每一对对应段互为反向取反。切口位置相同，这使两行字符串可以合成一个回文问题。

记 C 为仅将 V 的每个字符取反方向、保持原顺序的字符串，再构造长度为 n 的交织串：

T=U_0C_0U_1C_1\dots U_{h-1}C_{h-1}

考虑 U,V 中同一个左闭右开区间 [a,b)。两段互为反向取反，当且仅当对每个 j=0\sim b-a-1，都有 U_{a+j}=C_{b-1-j}。这又恰好等价于 T 的子串 [2a,2b) 是回文：翻转交织串时，U 的字符正好与逆序的 C 字符相对。

所以，原问题的一次合法划分，对应将 T 分成两段或三段非空回文串，并要求每个切口都在偶数下标处；反方向也成立。每段长度至少为 2，对应原串的一个非空块，不会引入空块。

定义 f_{i,j} 为将 T 的前 i 个字符划分成 j 段的方案数，所有切口均在偶数下标处，每段均为非空回文。仅需维护 j=0\sim 3。初始状态为 f_{0,0}=1，其他状态为 0。

当 i 为奇数时，固定令 f_{i,j}=0；当 i 为偶数时，枚举当前前缀的每个非空回文后缀，将它作为最后一段。若其长度为 l，转移贡献为 f_{i-l,j-1}。奇数长度的回文会查询奇数前缀的状态，贡献自动为 0，不需要额外筛选。

当前循环起点的答案就是 f_{n,2}+f_{n,3}。直接枚举每个位置的全部回文后缀，在大量重复字符时会退化，因此用回文树和等差链接优化这一求和。

回文树节点 v 表示一个不同的回文，长度记为 L_v。其最长真回文后缀对应节点记为 p_v，由代码中的 nxt[v] 保存。定义相邻长度差 d_v=L_v-L_{p_v}。沿后缀链接，将长度差相同的连续节点归为一组。组内长度构成等差数列。

记 sl[v] 指向当前组之后的第一个节点。若 dif[v]==dif[nxt[v]]，当前节点与它的后缀链接在同一组，继承后者的等差链接；否则，等差链接直接指向后缀链接。代码中的 dif 保存 d_v。

在前缀长度为 i 时，设当前组最长节点为 v，等差链接指向 u，公差为 d_v。这一组最短回文的长度为 L_u+d_v，因此先取它的转移贡献：

g_{v,j}\gets f_{i-L_u-d_v,j-1}

若当前组还有其他节点，则加入已经保存的 g[nxt[v]][j]。这里复用的是较早前缀的组和，而非当前前缀中重新计算的值。组内回文以 d_v 为长度间隔：在长度为 i-d_v 的前缀中，nxt[v] 对应的组，与当前组除去最短回文后的部分一一对应。前缀长度和所取回文长度同时减少 d_v，被查询的状态下标 i-l 保持不变，因此转移权值可以直接复用。

等差链接的遍历仅访问每一组的最长节点，保证 g[nxt[v]] 保留上述所需的历史组和。若相邻长度差不同，当前组仅有一个节点，不加入这项。将每组得到的 g_{v,j} 累加，就完成当前状态的全部回文后缀转移。

这里有一个与偶数切口有关的实现细节：即使当前前缀长度为奇数，也必须更新各组的 g，因为后续偶数位置可能复用这些历史组和。仅最终写入 f 时限制前缀长度为偶数，不能跳过奇数位置的整个回文树过程，也不能每读入一个字符就清空 g。

题面还保证边界行走除首尾外不重复坐标，所以不同循环起点得到的方向串两两不同。若存在小于 n 的循环周期 p，完整串就是同一长度为 p 的块重复 n/p 次。完整路径位移为零，使每一块的位移也为零，于是走完第一块便回到起点，与边界条件矛盾。因此枚举全部起点不会重复统计相同的移位串。

枚举循环起点时还能减少一半计算。若某个移位的分解为 XYZ\overline{X}\overline{Y}\overline{Z}，再移动 h 个字符后，它的分解为 \overline{X}\overline{Y}\overline{Z}XYZ；两段形式同理。这个变换保留所有块长，且执行两次恢复原分解，因此两个起点的方案数一一对应。仅计算前 h 个循环起点，将总和乘以 2 即可。

代码把上、右、下、左依次编码为 0,1,2,3，反方向通过异或 2 得到。回文树使用长度为 0 和 -1 的两个根节点，a[0]=-1 作为越界匹配的哨兵。每个循环起点重新建立交织串和回文树，清空该轮的状态与组和，避免不同移位之间共享历史。

回文后缀的周期性质保证等差组数量为 O(\log n)，每组仅处理三个段数状态。因此每个移位需要 O(n\log n)，总时间复杂度为 O(n^2\log n)，空间复杂度为 O(n)。单个移位最多枚举两个切口，状态值可以使用 int；汇总全部移位的答案使用 long long。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=10005;
int a[N],b[N],ch[N][4],len[N],nxt[N],dif[N],sl[N],f[N][4],g[N][4];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    string s;
    cin>>n>>s;
    for(int i=0;i<n;i++)b[i]=string("urdl").find(s[i]);
    ll ans=0;
    for(int i=0;i<n/2;i++)
    {
        for(int j=0;j<n/2;j++)
        {
            a[j*2+1]=b[(i+j)%n];
            a[j*2+2]=b[(i+j+n/2)%n]^2;
        }
        memset(ch,0,sizeof ch);
        memset(f,0,sizeof f);
        memset(g,0,sizeof g);
        a[0]=-1;
        len[0]=0;
        len[1]=-1;
        nxt[0]=1;
        nxt[1]=0;
        dif[0]=dif[1]=0;
        sl[0]=sl[1]=0;
        f[0][0]=1;
        int cnt=1,last=0;
        for(int j=1;j<=n;j++)
        {
            int u=last;
            while(a[j-len[u]-1]!=a[j])u=nxt[u];
            if(!ch[u][a[j]])
            {
                cnt++;
                ch[u][a[j]]=cnt;
                len[cnt]=len[u]+2;
                int v=nxt[u];
                while(a[j-len[v]-1]!=a[j])v=nxt[v];
                nxt[cnt]=len[cnt]==1?0:ch[v][a[j]];
                dif[cnt]=len[cnt]-len[nxt[cnt]];
                sl[cnt]=dif[cnt]==dif[nxt[cnt]]?sl[nxt[cnt]]:nxt[cnt];
            }
            last=ch[u][a[j]];
            for(int k=last;len[k]>0;k=sl[k])
            {
                int pos=j-len[sl[k]]-dif[k];
                for(int i=1;i<=3;i++)
                {
                    g[k][i]=f[pos][i-1];
                    if(dif[k]==dif[nxt[k]])g[k][i]+=g[nxt[k]][i];
                    if(j%2==0)f[j][i]+=g[k][i];
                }
            }
        }
        ans+=f[n][2]+f[n][3];
    }
    cout<<ans*2<<'\n';
    return 0;
}