upd on 2021.10.20:修了个 typo(
这是一道 *2600 的 D2E,然鹅为啥我没想到呢?wtcl/dk
首先第一步我就没想到/kk,看到“恰好”二字我们可以想到一个东西叫做二项式反演(qwq 这个套路在刷多项式题时经常见到,可咋换个场景就想不到了呢?显然是我多项式白学了/doge)。我们设 \(f_k\) 表示恰好 \(k\) 个完美数的排列个数,\(g_k\) 表示钦定 \(k\) 个位置满足 \(|p_i-i|=1\),剩下随便乱填的方案数,那么显然对于某个有 \(x\) 个完美位置的排列,它被计入 \(g_y(y<x)\) 的次数为 \(\dbinom{x}{y}\)。
也就是说 \(g_k=\sum\limits_{i=k}^nf_i\dbinom{i}{k}\)。反演一下可得 \(f_k=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}g_i\)。
故我们只需求出 \(g_i\) 就行了。
怎么求 \(g_i\) 呢?这时候就要用到 DP 了,我们设 \(dp_{i,j,x,y}\) 表示填好了前 \(i\) 个位置,钦定了 \(j\) 个位置满足 \(|p_i-i|=1\),\(x\) 表示 \(i\) 是否被选择,\(y\) 表示 \(i+1\) 是否被选择(这一步我又没想到,看来我 DP 也白学了/ww)。转移就分 \(i\) 不是被钦定为“完美位置”,\(p_i=i+1,p_i=i-1\) 三种情况转移即可,具体来说:
初始 \(dp_{1,0,0,0}=dp_{1,1,0,1}=1\)。
最后 \(g_k=(dp_{n,k,0,0}+dp_{n,k,1,0})·(n-k)!\)(\(n+1\) 不能被选择),时间复杂度 \(n^2\)。
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fill0(a) memset(a,0,sizeof(a))
#define fill1(a) memset(a,-1,sizeof(a))
#define fillbig(a) memset(a,63,sizeof(a))
#define pb push_back
#define ppb pop_back
#define mp make_pair
template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}
template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned int u32;
typedef unsigned long long u64;
namespace fastio{
#define FILE_SIZE 1<<23
char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;
inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}
inline void putc(char x){(*p3++=x);}
template<typename T> void read(T &x){
x=0;char c=getchar();T neg=0;
while(!isdigit(c)) neg|=!(c^'-'),c=getchar();
while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(neg) x=(~x)+1;
}
template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}
template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}
void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}
}
const int MAXN=1000;
const int MOD=1e9+7;
int n,m,dp[MAXN+5][MAXN+5][2][2];
int fac[MAXN+5],ifac[MAXN+5];
void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;}
int binom(int x,int y){return 1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
int main(){
scanf("%d%d",&n,&m);dp[1][1][0][1]=dp[1][0][0][0]=1;
fac[0]=1;ifac[0]=ifac[1]=1;
for(int i=2;i<=n;i++) ifac[i]=1ll*ifac[MOD%i]*(MOD-MOD/i)%MOD;
for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%MOD,ifac[i]=1ll*ifac[i-1]*ifac[i]%MOD;
for(int i=2;i<=n;i++) for(int j=0;j<=i;j++){
if(j){
add(dp[i][j][0][0],dp[i-1][j-1][0][0]);
add(dp[i][j][1][0],dp[i-1][j-1][0][1]);
add(dp[i][j][0][1],dp[i-1][j-1][0][0]);
add(dp[i][j][0][1],dp[i-1][j-1][1][0]);
add(dp[i][j][1][1],dp[i-1][j-1][0][1]);
add(dp[i][j][1][1],dp[i-1][j-1][1][1]);
}
add(dp[i][j][0][0],dp[i-1][j][0][0]);
add(dp[i][j][0][0],dp[i-1][j][1][0]);
add(dp[i][j][1][0],dp[i-1][j][0][1]);
add(dp[i][j][1][0],dp[i-1][j][1][1]);
} int ans=0;
for(int i=m;i<=n;i++){
int ways=1ll*(dp[n][i][0][0]+dp[n][i][1][0])*fac[n-i]%MOD;
if((i-m)&1) ans=(ans-1ll*ways*binom(i,m)%MOD+MOD)%MOD;
else ans=(ans+1ll*ways*binom(i,m))%MOD;
} printf("%d\n",ans);
return 0;
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章