[数学记录]AT2062 [AGC005D] ~K Perm Counting
command_block
2021-01-12 08:49:30
**题意** ： 若排列 $P$ 满足 $|P_i-i|≠k$ 则称为好的。
给出 $n=|P|,k$ ，求有多少个好的排列。
答案对 $924844033$ （素数）取模。
$n\leq 2000$ ，时限 $\texttt{2s}$。
------------
考虑容斥。
设 $f(t)$ 为钦定 $t$ 个位置满足 $|P_i-i|=k$ 的方案数。
可以将排列看成完全二分图的一个匹配，若要求 $|P_i-i|=k$ （称作限定点），则相当于只有两个出边。
我们把若干个限定点按照两出边串在一起（表示可能产生冲突），就形成了链条。
不难发现模 $2k$ 同余的两个位置才可能串联，考虑模分类。
对于一个大小为的同余类，两个相邻的限定点必然串联。即限定点的可选边是一条链。
此时，若链中边数为 $m$ ，在这样一条链上选出一个大小为 $t$ 的匹配（即 $t$ 个限定点及其匹配）的方案数为 $\dbinom{m-i+1}{i}$ （类插板法）
我们是在很多个同余类上选，所以还要来个背包合并。
一条链的 $\rm OGF$ 为 $\sum\limits_{i=0}\dbinom{m-i+1}{i}x^i$。
然后将各个链的 $\rm OGF$ 卷积即可得到答案。
暴力卷积，一个同余类的大小为 $O(n/k)$，共 $O(k)$ 个，故复杂度为 $O(n*(n/k)*k)=O(n^2)$。
（这一步可以用多项式科技加速）
最终计算出钦定 $t$ 个关键点及其匹配的方案数为 $P[t]$。
在限定点决策完毕后，其余的点可以随意，方案数为 $(n-t)!$。
则 $f(t)=(n-t)!P[t]$。
最终 ${\rm Ans}=\sum\limits_{t=0}^n(-1)^tf(t)$。
```cpp
#include<algorithm>
#include<cstdio>
#define ll long long
#define MaxN 2050
using namespace std;
const int mod=924844033;
ll powM(ll a,int t=mod-2){
ll ret=1;
while(t){
if (t&1)ret=ret*a%mod;
a=a*a%mod;t>>=1;
}return ret;
}
ll fac[MaxN],ifac[MaxN];
ll C(int n,int m){
if (m<0||n<m)return 0;
return fac[n]*ifac[m]%mod*ifac[n-m]%mod;
}
void Init(int n)
{
fac[0]=1;
for (int i=1;i<=n;i++)
fac[i]=fac[i-1]*i%mod;
ifac[n]=powM(fac[n]);
for (int i=n;i;i--)
ifac[i-1]=ifac[i]*i%mod;
}
int n,k;
ll S[MaxN],G[MaxN];
int main()
{
scanf("%d%d",&n,&k);
Init(n+1);
S[0]=1;
for (int r=1;r<=min(2*k,n);r++){
int m=(r>k)-1;
for (int i=r;i<=n;i+=k)m++;
for (int i=0;i<=n;i++)
{G[i]=S[i];S[i]=0;}
for (int i=0;i<=m;i++){
ll buf=C(m-i+1,i);
for (int j=0;i+j<=n;j++)
S[i+j]=(S[i+j]+buf*G[j])%mod;
}
}
ll ans=0;
for (int t=0;t<=n;t++){
ll buf=fac[n-t]*S[t]%mod;
if (t&1)ans-=buf;else ans+=buf;
}printf("%lld",(ans%mod+mod)%mod);
return 0;
}
```