题解：P11316 [RMI 2021] 去 M / NoM

_Ch1F4N_ · 2024-11-24 03:16:09 · 题解

首先标号什么的最后再考虑，先只对无标号（但是区分颜色）方案算，等于说你要把 [1,2 \times n] 对半染色再匹配。

对好方案算不太方便，考虑算所有坏方案，其实这个也不方便，但是我们可以容斥，不妨 dp_i 表示至少有 i 对距离为 m 倍数的匹配的方案，所有坏方案就是 \sum_i dp_i \times (-1)^{i+1}。问题变成如何求解 dp_i。

要对距离为 m 倍数的匹配相关计数，注意到距离为 m 倍数时匹配的两个位置模 m 同余并且不同余数间互不影响，对于每个余数求出 dp 数组后再合并的过程可以视作一个树上背包，不难发现其是 O(n^2) 的。

最后的问题就是 2 \times t 个数对半染色再两两匹配的方案数，先确定每种颜色的集合再确定匹配，可以得到方案数就是 {{2 \times t} \choose t} \times t!，预处理下组合数即可做到 O(n^2)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 1e9+7;
const int maxn = 4e3+114;
int fac[maxn],inv[maxn];
int iv[maxn];
int qpow(int a,int b){
    if(b==0) return 1;
    if(b==1) return a;
    int res=qpow(a,b/2);
    res=res*res%mod;
    if(b%2==1) res=res*a%mod;
    return res;
}
int dp[maxn];//全局选取 j 对的方案
int C(int n,int m){
    if(n<m) return 0;
    return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int n,m,ans;
signed main(){
    fac[0]=inv[0]=1;
    for(int i=1;i<maxn;i++) fac[i]=fac[i-1]*i%mod,inv[i]=qpow(fac[i],mod-2);
    cin>>n>>m;
    n*=2;
    ans=C(n,n/2)*fac[n/2]%mod;
    if(n<=m){
        cout<<ans*fac[n/2]%mod<<'\n';
        return 0;
    }
    dp[0]=1;
    int sum=0;
    for(int p=0;p<m;p++){
        int cnt=(n-p)/m+(p==0?0:1);
        for(int i=sum;i>=0;i--){
             for(int j=1;j*2<=cnt;j++) dp[i+j]=(dp[i+j]+dp[i]*C(cnt,j*2)%mod*C(j*2,j)%mod*fac[j]%mod)%mod;
        }
        sum+=(cnt/2);
    }
    for(int j=1;j<=sum;j++){
        if(n-2*j!=0) dp[j]=dp[j]*C(n-2*j,(n-2*j)/2)%mod*fac[(n-2*j)/2]%mod;
        ans=(ans+dp[j]*(j%2==0?1:(mod-1))%mod)%mod;
    }
    cout<<ans*fac[n/2]%mod<<'\n';
    return 0;
}