题解 P5417【[CTSC2016]萨菲克斯·阿瑞】
whiteqwq
·
·
题解
P5417 [CTSC2016]萨菲克斯·阿瑞 解题报告：
更好的阅读体验
3000 AC。
题意
计数长度为 n，字符集大小为 m，且每个字符出现次数不超过 c_i 的 SA 数量。
## 分析
直接对 SA 的定义计数看上去就无从下手，考虑找一个性质转化。
考虑排序后相邻的两个后缀 $p_i,p_{i+1}$（$p$ 就是 SA 数组），显然有 $s_{p_i}\leqslant s_{p_{i+1}}$。若取等，那么就要求 $p_i+1$ 对应的后缀在 SA 内的位置比 $p_{i+1}+1$ 对应的后缀前，否则没有要求。
可以发现上面那个性质也是充分的，即：
**若 $p_i+1$ 在 SA 中的位置比 $p_{i+1}+1$ 前，那么 $s_{p_i}\leqslant s_{p_{i+1}}$，否则 $s_{p_i}<s_{p_{i+1}}$。**
可以将这些限制看成一个不等式链，我们现在想要对于每个合法的不等式链，计数其对应 SA 数量之和。
先考虑一个简单一些的问题，怎么判定一个不等式链合法：
用小于号将链分成若干段，每一段都贪心地填充，拿出最小的字符，能填完这个字符就填完，否则把这一段剩下的位置全部填满，然后丢掉这个字符。合法的条件就是能顺利进行这个过程。
然后考虑怎么计数：
小于号很烦人，于是我们容斥有哪些小于号变成了等于号，计算等于号和小于等于号的不等式链对应的 SA 数量。
手玩观察（？）可得方案数应为：按照没有改变的小于号分段，每一段的长度共同形成的多重组合数。
带上容斥系数，这个的贡献应该是这样的一个形式：（$m-k$ 就是等号的数量）
$$(-1)^{m-k}{n\choose l_1,l_2,\cdots,l_k}$$
考虑 dp 容斥系数和（这个歌过程类似于不等式链的判定），令 $f_{r,i,j}$ 表示只塞入 $1$ 到 $r$ 的字母，放了 $i$ 个位置进去，目前的段长度为 $k$ 的容斥系数和。
转移：
1. 用字母 $r$ 填满这一段，然后分段：$$f_{r+1,i+k,0}\leftarrow \frac{1}{(j+k)!}\cdot f_{r,i,j}$$
2. 把字母 $r$ 填完：$$f_{r,i+c_r,j+c_r}\leftarrow f_{r,i,j}$$
3. 钦定一个等号：$$f_{r,i+k,j+k}\leftarrow (-1)\cdot f_{r,i,j}$$
可以发现第二类转移和第三类转移能合并，$k$ 的范围从 $[1,c_r]$ 改为 $[1,c_r)$ 即可。
两类转移都可以用前缀和优化一下，于是复杂度就是 $O(n^2m)$ 了。
## 代码
记得把 $c=0$ 的字母去掉。
```cpp
#include<stdio.h>
const int maxn=505,mod=1000000007;
int n,m,M,ans;
int c[maxn],C[maxn],f[maxn][maxn],sum[maxn][maxn],fac[maxn],inv[maxn],nfac[maxn];
int main(){
scanf("%d%d",&n,&M);
fac[0]=nfac[0]=1;
for(int i=1;i<=n;i++)
fac[i]=1ll*fac[i-1]*i%mod,inv[i]=i==1? 1:(mod-1ll*(mod/i)*inv[mod%i]%mod),nfac[i]=1ll*nfac[i-1]*inv[i]%mod;
for(int i=1;i<=M;i++){
scanf("%d",&C[i]);
if(C[i])
c[++m]=C[i];
}
f[0][0]=1;
for(int r=1;r<=m;r++){
for(int i=0;i<=n;i++)
for(int j=0;j<=i;j++)
sum[i][j]=((i==0||j==0? 0:sum[i-1][j-1])+f[i][j])%mod,f[i][j]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++){
f[i][0]=(f[i][0]+1ll*nfac[j]*(sum[i-1][j-1]-(j<=c[r]? 0:sum[i-c[r]-1][j-c[r]-1])+mod))%mod;
f[i][j]=(0ll+f[i][j]-(sum[i-1][j-1]-(j<c[r]? 0:sum[i-(c[r]-1)-1][j-(c[r]-1)-1]))+mod)%mod;
}
ans=(ans+f[n][0])%mod;
}
printf("%d\n",1ll*ans*fac[n]%mod);
return 0;
}
```