你说别追啊 又依依不舍/所以生命啊 它苦涩如歌
jun头吉吉
·
·
题解
题意
给定 N,K,P。
称一个长度为 K 的数组 \{a_i\} 是好的当且仅当 1\le a_i\le i。
称一个长度为 NK 的数组 \{b_i\} 是合法的当且仅当可以被分成 N 个长度为 K 的子序列，每个都是好的。
设 f(pos,val) 表示 b_{pos}=val 的合法序列数。对 1\le pos\le NK,1\le val\le K 求出 f(pos,val)\bmod P。
## 题解
首先考虑怎么判定一个数组是不是合法的。一个显然的贪心策略是维护长度为 $N$ 的序列 $\{c_j\}$，初始值全部为 $K$，也就是每个序列没有填的长度。从后往前遍历 $b_i$，找到最小的 $c_j\ge b_i$，把 $c_j$ 减去 $1$。如果没有 $c_j$ 那么就是不合法。
这个找到最小的 $c_j\ge b_i$ 不方便计数，我们换一种方式，也就是设 $c_i'=\sum_j [c_j<i]$，初始全部是 $0$，每次就是让 $c'_{b_i}$ 加 $1$，如果已经是 $N$ 那么就不合法，然后从小到大排序。
这个为什么是对的呢。考虑找到最小的 $c_j\ge b_i$ 就相当于找最小 $x\ge b_i,c'_{x+1}\ne c'_x$，然后把 $c_x'$ 加上一。发现既然 $c'_{b_i}$ 到 $c_x'$ 都是相等的，那么加哪个都是一样的。
这个的好处就在于，如果 $b_i$ 的取值为 $[1,K]$，那么甚至不需要排序。唯一需要排序的一次是在 $pos$ 的时候，因为要保证 $c_{b_{pos}}'<N$。
那么就可以计数了。设到 $pos$ 时的数组为 $\{c_i'\}$，那么对应的贡献是：
$$
\sum_{\tiny\begin{aligned}&0\le c_1'\le c_2'\le\dots\le c_K'\le N\\ &\sum c_i'=NK-pos\end{aligned}}\frac{K!}{\prod_{i=0}^n(\sum_j [c_j'=i])!}\times\frac{(NK-pos)!}{\prod_{i=1}^K c_i'!}\times\frac{(pos-1)!}{\prod_{i=1}^K(N-c_i'-[i=val])!}
$$
第一项的含义是把序列重排的方案数，第二项的含义是 $b_{NK}$ 到 $b_{pos+1}$ 这 $NK-pos$ 次的分配方案，第三项的含义是 $b_{pos-1}$ 到 $b_1$ 这 $pos-1$ 次的分配方案。
枚举 $val$ 然后dp即可，设 $f_{x,y,z}$ 表示选 $\le x$ 的数，共 $y$ 个，和为 $z$，的贡献和。转移就是枚举 $x$ 选了几个。复杂度 $\mathcal O(N^2K^4)$。
## 代码
```cpp
const int N=21;
int n,k;mint dp[2][N][N*N],fac[N*N],ifac[N*N];
mint res[N*N][N];
signed main(){
read(n,k,mod);
fac[0]=ifac[0]=1;for(int i=1;i<N*N;i++)fac[i]=fac[i-1]*i,ifac[i]=1/fac[i];
for(int val=1;val<=k;val++){
memset(dp,0,sizeof dp);
int cur=0,pre=1;
dp[cur][0][0]=1;
for(int x=0;x<=n;x++){
swap(pre,cur);memset(dp[cur],0,sizeof dp[cur]);
for(int y=0;y<=k;y++)for(int z=0;z<=n*k;z++)if(dp[pre][y][z].x){
mint _=ifac[x]*ifac[n-x],v=dp[pre][y][z];
for(int c=0;z+c*x<=n*k&&y+c<=k&&v.x;c++,v*=_,(y+c==val)&&(v*=(n-x)).x)
dp[cur][y+c][z+c*x]+=v*ifac[c];
}
for(int pos=1;pos<=n*k;pos++)res[pos][val]=fac[k]*fac[n*k-pos]*fac[pos-1]*dp[cur][k][n*k-pos];
}
}
for(int pos=1;pos<=n*k;pos++)for(int val=1;val<=k;val++)
write(res[pos][val].x),pc(" \n"[val==k]);
}
```