题解：P10004 [集训队互测 2023] Permutation Counting 2
ini2015_____
·
·
题解
纯真计数题，为啥我做不出来，悲愤了。
首先考虑一个简单问题，对于一个序列 p，长度为 n，值域为 [1,m]，求
f(m,k)=\sum_p\Big[\sum_{i=1}^{n-1}[p_i\le p_{i+1}]=k\Big]
稍微做一个转化，有 n-k-1 个位置满足 p_i> p_{i+1}，那么我们实际上把 n 个数划分成了 n-k 个上升连续段。
考虑对 k 二项式反演，记 g(m,i) 为钦定 i 个上升连续段的方案数，那么有
f(m,n-k)=\sum_{i=0}^k(-1)^{k-i}\binom {n-i}{n-k}g(m,i)
::::info[什么叫钦定连续段？]
ZFR 提出的问题，感觉这里讲的不是很清楚。
其实钦定连续段就是钦定连续段之间的插板啦，后面的二项式反演都是对插板进行反演的。
::::
考虑求出 g(m,i)，不难发现一个上升连续段和其桶数组构成双射，那么我们认为有 i\times m 的一个矩阵 A，A_{i,j} 表示第 i 个连续段里第 j 个数出现了 A_{i,j} 次。
那么 g(m,i) 就是一个 i\times m 的矩阵填数，和为 n，每一行不能为空的方案数。
依旧二项式反演，我们钦定有 j 行是空的，贡献是
g(m,i)=\sum_{j=0}^i (-1)^j\binom ij\binom{(i-j)m+n-1}{n}
于是就能愉快算出来 f 了。
回到原问题，记 p 的逆排列为 q，我们希望 p 有 n-x 个上升连续段，q 有 y 个位置满足 q_{i}<q_{i+1}。
先做第一维的二项式反演，我们钦定 p 有 k 个上升连续段，记此时的方案数为 F(n-k,y)。
不妨给 p 的每个上升连续段标号，按照其在 p 中的顺序，一次编号 1,2,3\dots k，j 的编号记作 id_j，那么 q_i<q_{i+1}\iff id_i\le id_{i+1}。
然后一个难以发现的事情是，id 和 q 建立了一个双射！
那么我们只需要对 id 计数即可。
那么再次二项式反演，钦定有 $j$ 种数不出现，那么有
$$F(n-k,y)=\sum_{j=0}^k (-1)^{j}\binom kjf(k-j,y)$$
记我们要求的答案为 $G(x,y)$，那么显然有
$$G(x,y)=\sum_{k=x}^{n-1}(-1)^{k-x}\binom kxF(k,y)$$
每一个部分都是 $O(n^3)$ 的，可以通过 $n=500$。
如果需要卡常的话，可以把 $n\le 500$ 的组合数预处理出来，实测效果很好。
::::info[code]
```
int Cx[M][M];
inline int C(int m,int n){
if(m<0||n<0||m<n)return 0;
if(m<M&&n<M){
if(Cx[m][n])return Cx[m][n];
return Cx[m][n]=1ll*fac[m]*ifac[m-n]%mod*ifac[n]%mod;
}
return 1ll*fac[m]*ifac[m-n]%mod*ifac[n]%mod;
}
int f[M][M],g[M][M];
int F[M][M],G[M][M];
inline void upd(int& x){if(x>=mod)x-=mod;}
inline int add(int x,int y){upd(x+=y); return x;};
inline int del(int x,int y){upd(x+=mod-y); return y;}
int main(){
n=read(),mod=read();
if(n==1){puts("1"); return 0;}
initfac();
for(int m=0;m<=n;m++)for(int i=0;i<=n;i++){
int& w=g[m][i];
for(int j=0;j<=i;j++){
int v=1ll*C(i,j)*C((i-j)*m+n-1,n)%mod;
if(j&1)upd(w+=mod-v);
else upd(w+=v);
}
}
for(int m=0;m<=n;m++)for(int k=0;k<=n;k++){
int& w=f[m][n-k];
for(int i=1;i<=k;i++){
int v=1ll*C(n-i,n-k)*g[m][i]%mod;
if((k-i)&1)upd(w+=mod-v);
else upd(w+=v);
}
}
for(int k=0;k<=n;k++)for(int y=0;y<=n;y++){
int& w=F[n-k][y];
for(int j=0;j<=k;j++){
int v=1ll*C(k,j)*f[k-j][y]%mod;
if(j&1)upd(w+=mod-v);
else upd(w+=v);
}
}
for(int x=0;x<=n;x++)for(int y=0;y<=n;y++){
int& w=G[x][y];
for(int k=x;k<n;k++){
int v=1ll*C(k,x)*F[k][y]%mod;
if((k-x)&1)upd(w+=mod-v);
else upd(w+=v);
}
}
for(int x=0;x<n;x++){
for(int y=0;y<n;y++)
printf("%d ",G[x][y]);
printf("\n");
}
return 0;
}
// Think twice,code once
```
::::