自动搬运

查看原文

来自洛谷，原作者为

	Ch1F4N HN 初三最菜 OIer|| 新的赛季 rp ++

搬运于2025-08-24 23:06:22，当前版本为作者最后更新于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;
}