AGC005D ~K Perm Counting
Dreamunk
2020-08-21 15:55:45
[题目](https://www.luogu.com.cn/problem/AT2062)
如果你看过一些关于组合数学的书，你可能会想到，这种排列计数可以对应到这样的图上：
所求的排列个数，就等于在这样的棋盘格子内放 $n$ 个互不攻击的車，且阴影格子不能放的方案数。上图是 $n=7,k=2$ 的情况。
这又怎么求呢？考虑容斥。设 $f_i$ 表示我硬要在阴影里放 $i$ 个車，剩下随便放的方案数，那么答案等于 $\sum_{i=0}^n (-1)^if_i(n-i)!$ 。
那现在只要求 $f_i$ 就好了。
考虑现在的还有什么限制，你发现同一行同一列的阴影格子还是不能同选。把不能同选的格子连上边：
那 $f_i$ 其实就是这个图大小为 $i$ 的独立集个数。
很明显这个图就是若干条链。
考虑把这些链连起来。转为求从这一排结点中选 $i$ 个，拼接的位置可以相邻，其他位置不能相邻 的方案数。于是它变为了一个简单的 DP 问题。
$O(n^2)$ 解决。
当然这题可以用多项式方法做到 $O(n\log n)$。不讲。
```cpp
#include<cstdio>
typedef long long ll;
const int N=2003,M=924844033;
int n,m,fac[N],f[N+N][N],t,a[N+N],ans;
int main(){
scanf("%d%d",&n,&m);
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=(ll)fac[i-1]*i%M;
a[t=0]=1;
for(int i=1;i<=(n-m)%m;i++)
a[t+=(n-m)/m+1]=1,a[t+=(n-m)/m+1]=1;
for(int i=1;i<=m-(n-m)%m;i++)
a[t+=(n-m)/m]=1,a[t+=(n-m)/m]=1;
f[0][0]=1;
for(int i=1;i<=t;i++)
for(int j=0;j<=n;j++)
f[i][j]=(f[i-1][j]+(j?f[i-1-(!a[i-1])][j-1]:0))%M;
for(int j=0;j<=n;j++)
ans=(ans+(ll)f[t][j]*fac[n-j]%M*(j&1?M-1:1))%M;
printf("%d\n",ans);
return 0;
}
```