LIII.CF285E Positions in Permutations
神题orz……
我也是第一次听说有个叫二项式反演的神奇东西……
它具体有两个形式：
-
\(F(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}G(i)\Leftrightarrow G(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}F(i)\)
-
\(F(n)=\sum\limits_{i=0}^n\dbinom{n}{i}G(i)\Leftrightarrow G(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}F(i)\)
-
\(F(n)=\sum\limits_{i=n}^?(-1)^i\dbinom{i}{n}G(i)\Leftrightarrow G(n)=\sum\limits_{i=n}^?(-1)^i\dbinom{i}{n}F(i)\)
-
\(F(n)=\sum\limits_{i=n}^?\dbinom{i}{n}G(i)\Leftrightarrow G(n)=\sum\limits_{i=n}^?(-1)^{i-n}\dbinom{i}{n}F(i)\)
这题可以考虑设\(G(i)\)表示“完美数”恰好为\(i\)的方案数，再设\(F(i)\)表示“完美数”\(\geq i\)的方案数。
肯定有\(F(m)=\sum\limits_{i=m}^n?\times G(i)\)，其中\(?\)是某个系数。
则对于\(G(i)\)中的某种方案，我们需要从\(i\)个位置中挑出\(m\)个位置，然后只观察这\(m\)个位置而忽略其它地方。显然，共有\(\dbinom{i}{m}\)种方法。
因此有\(F(m)=\sum\limits_{i=m}^n\dbinom{i}{m}G(i)\)。
套用4，得到\(G(m)=\sum\limits_{i=m}^n(-1)^{i-m}\dbinom{i}{m}F(i)\)。
考虑DP求\(F\)。
我们设\(f[i][j][k=0/1][l=0/1]\)表示：
前\(i\)位，有\(j\)个完美数，并且数字\(i\)选没选的状态是\(k\)，数字\(i+1\)选没选的状态是\(l\)的方案数。
需要注意的是，我们只注意完美的位置，至于其它位置填什么吗……最后阶乘一下。
因此有：
- 第\(i\)位是完美位
1.1. 填入\(i-1\)
则有
\(f[i][j][0][0]+=f[i-1][j-1][0][0]\)
\(f[i][j][1][0]+=f[i-1][j-1][0][1]\)
1.2.填入\(i+1\)
则有
\(f[i][j][0][1]+=f[i-1][j-1][0][0]+f[i-1][j-1][1][0]\)
\(f[i][j][1][1]+=f[i-1][j-1][0][1]+f[i-1][j-1][1][1]\)
- 第\(i\)位空置
则有
\(f[i][j][0][0]+=f[i-1][j][0][0]+f[i-1][j][1][0]\)
\(f[i][j][1][0]+=f[i-1][j][0][1]+f[i-1][j][1][1]\)
然后特殊转移：
1.第\(1\)位：
1.1.空置：\(f[1][0][0][0]=1\)
1.2.放\(i+1\)：\(f[1][1][0][1]=1\)
（注意，这里不需要特别讨论放\(i\)的情况——这就是为什么\(F(i)\)的定义是\(\geq i\)的方案数）
2.第\(n\)位
废去1.2.填入\(i+1\)的方案即可。
最终有\(F(i)=(n-i)!(f[n][i][0][0]+f[n][i][1][0])\)
因为除了完美位外其它的位置都是可以阶乘随便填的。
然后套我们之前的式子，
\(G(m)=\sum\limits_{i=m}^n(-1)^{i-m}\dbinom{i}{m}F(i)\)
即可。
（如果要求所有\(G(m)\)可以直接FFT卷积，不过这题不需要罢了）
代码：
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n,m,f[1010][1010][2][2],fac[1010],inv[1010],F[1010],res;
int ksm(int x,int y){
int z=1;
for(;y;y>>=1,x=(1ll*x*x)%mod)if(y&1)z=(1ll*z*x)%mod;
return z;
}
int C(int x,int y){
return 1ll*fac[x]*inv[y]%mod*inv[x-y]%mod;
}
int main(){
scanf("%d%d",&n,&m),f[1][0][0][0]=f[1][1][0][1]=1;
fac[0]=1;
for(int i=1;i<=n;i++)fac[i]=(1ll*fac[i-1]*i)%mod;
inv[n]=ksm(fac[n],mod-2);
for(int i=n-1;i>=0;i--)inv[i]=(1ll*inv[i+1]*(i+1))%mod;
for(int i=2;i<=n;i++)for(int j=0;j<=i;j++){
if(j){
f[i][j][0][0]=f[i-1][j-1][0][0];
f[i][j][1][0]=f[i-1][j-1][0][1];
if(i<n)f[i][j][0][1]=(f[i-1][j-1][0][0]+f[i-1][j-1][1][0])%mod;
if(i<n)f[i][j][1][1]=(f[i-1][j-1][0][1]+f[i-1][j-1][1][1])%mod;
}
f[i][j][0][0]=(0ll+f[i][j][0][0]+f[i-1][j][0][0]+f[i-1][j][1][0])%mod;
f[i][j][1][0]=(0ll+f[i][j][1][0]+f[i-1][j][0][1]+f[i-1][j][1][1])%mod;
}
for(int i=0;i<=n;i++)F[i]=1ll*fac[n-i]*(f[n][i][0][0]+f[n][i][1][0])%mod;
for(int i=m;i<=n;i++)(res+=(((i-m)&1?-1ll:1ll)*(1ll*C(i,m)*F[i]%mod)+mod)%mod)%=mod;
printf("%d\n",res);
return 0;
}