题解：P16244 【MX-X27-T5】重叠
lailai0916
·
·
题解
题意简述
给定偶数长度 n。对每个有序合法括号序列对，保留两串对应位置相同的字符。统计提取结果的层数分别为 1\sim\frac{n}{2} 时的序列对数量。
解题思路
把左、右括号分别记为 1,-1。设两条原序列在读完前 i 个字符后的前缀和为 x_i,y_i。若当前位置字符相同，两个前缀和的增量之和为 2 或 -2。提取序列相应增加左括号或右括号。若字符不同，增量之和为 0，也不会提取字符。因此，扫描到原串位置 i 时，提取序列的前缀和为：
\frac{x_i+y_i}{2}
由于 x_i,y_i 始终非负且最终均为 0，提取结果一定是合法括号序列。它的层数就是上述前缀和的最大值。
记层数不超过 d 的序列对数量为 F_d。最终需要输出 F_d-F_{d-1}。两个合法括号序列的首字符都是左括号，所以提取结果非空，即 F_0=0。
接下来计算 F_d。将两条前缀和路径各向上平移一格，令 p_i=x_i+1、q_i=y_i+1，并令 w=2d+4、r_i=w-q_i。原序列合法等价于 p_i>0 与 r_i<w。层数限制可以改写为：
p_i+q_i\le2d+2\iff p_i\le r_i-2
设 $P(u,v)$ 表示在 $(0,w)$ 内从高度 $u$ 走到 $v$ 的路径数。由非交路径行列式，结合上下对称性可得：
$$
F_d=P(1,1)^2-P(1,w-1)^2
$$
这里的减项也可以理解为交换终点的路径对。交换终点的两条路径必然相交。在第一次交点交换后缀，就与同终点路径对中的相交方案一一对应。
令 $m=\frac{n}{2}$、$h=d+2$，则 $w=2h$。对单条路径反复反射越过的上下边界，终点镜像会相隔 $2h$。从高度 $1$ 回到 $1$ 时，正负镜像对应的向上步数相差一；走到 $w-1$ 时，对应偏移为奇数倍的 $h$。因此：
$$
\begin{aligned}
P(1,1) & =\sum_{j\in\mathbb{Z}}\left(\binom{n}{m+2jh}-\binom{n}{m+2jh-1}\right) \\
P(1,w-1) & =\sum_{j\in\mathbb{Z}}\left(\binom{n}{m+(2j+1)h-1}-\binom{n}{m+(2j+1)h}\right)
\end{aligned}
$$
为了只枚举非负下标，定义：
$$
b_t=\binom{n}{m+t}-\binom{n}{m+t-1}
$$
由组合数的对称性 $inom{n}{m-t}=\binom{n}{m+t}$，有 $b_{-t}=-b_{t+1}$。把正负偏移配对后，上面两项分别化为：
$$
\begin{aligned}
P(1,1) & =b_0+\sum_{j\ge1}(b_{2jh}-b_{2jh+1}) \\
P(1,w-1) & =\sum_{j\ge0}(b_{(2j+1)h+1}-b_{(2j+1)h})
\end{aligned}
$$
当下标超过 $m+1$ 后，各项均为 $0$。预处理阶乘、逆阶乘和所有 $b_t$，再对每个 $h$ 枚举它的倍数即可。总枚举次数是调和级数，时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=407697;
const int mod=998244353;
int n;
int fac[N],jv[N],g[N];
ll Pow(ll x,ll y)
{
x%=mod;
ll res=1;
while(y)
{
if(y&1)res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
int C(int n,int m)
{
if(m<0||m>n)return 0;
return (ll)fac[n]*jv[m]%mod*jv[n-m]%mod;
}
void init()
{
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=(ll)fac[i-1]*i%mod;
jv[n]=Pow(fac[n],mod-2);
for(int i=n;i;i--)jv[i-1]=(ll)jv[i]*i%mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
init();
int m=n/2;
for(int i=0;i<=m+2;i++)g[i]=(C(n,m+i)-C(n,m+i-1)+mod)%mod;
int lst=0;
for(int i=1;i<=m;i++)
{
int h=i+2;
int x=g[0],y=0;
for(int j=2*h;j<=m+1;j+=2*h)x=(x+(ll)g[j]-g[j+1]+mod)%mod;
for(int j=h;j<=m+1;j+=2*h)y=(y+(ll)g[j+1]-g[j]+mod)%mod;
int cur=((ll)x*x%mod-(ll)y*y%mod+mod)%mod;
cout<<(cur-lst+mod)%mod<<(i==m?'\n':' ');
lst=cur;
}
return 0;
}
```