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

· · 题解

Solution

首先我们转化一下题意，我们把 2N 个位置按模 M 的余数分成 M 个类，当一个排列方式是好的实际上就是指每个编号的两个石子位于不同的类中。

第 i 个类（i 从 1 到 M）的大小就为：

w_i = \left\lfloor\frac{2N - i}{M}\right\rfloor + 1

我们设 dp[i][j] 表示考虑了前 i 个剩余类，已经成功放了 j 对石子（即 j 个编号的两个石子已经分到不同类中）的方案数。

考虑处理第 i 个类，该类有 w 个位置，设 s 为前 i-1 个类的石子总数。

在状态 dp[i-1][j] 下，已经有 j 对配对，放置了 2j 个石子，剩余单独的 s-2j 个石子分别属于不同的编号，所以已经出现至少一个石子的编号数就有 j + (s-2j) = s-j 个。

当前类要放 w 个石子，我们可以选择 k 个单独的石子，将它们各自的另一个石子放入当前类，则这 k 个编号满足要求，新增了 k 对；对于剩下的 w-k 个位置，从尚未出现的编号中选 w-k 个，放入它们的第一个石子，所以总的方案数就为：

\binom{s-2j}{k} \cdot \binom{N-(s-j)}{w-k}

易得转移方程为：

dp[i][j+k] \mathrel{+}= dp[i-1][j] \cdot \binom{s-2j}{k} \cdot \binom{N-(s-j)}{w-k}

当我们知道将所有 N 对石子成功配对的方案数后，还需要考虑

  1. 每个剩余类内部的 w_i 个位置上的石子可以任意排列，有 \prod_{i=1}^{M} w_i! 种方式。
  2. 每对石子中颜色可以互换，共 2^N 种方式。

所以最终答案就为：

\text{ans} = dp[M][N] \cdot \left(\prod_{i=1}^{M} w_i!\right) \cdot 2^N

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e3+5;
const int M=1e9+7;
int n,m,v[N],inv[N],dp[N][N];
int qpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%M;
        a=a*a%M;
        b>>=1;
    }
    return res;
}
void init(){
    v[0]=1;
    for(int i=1;i<N;i++){
        v[i]=v[i-1]*i%M;
    }
    inv[N-1]=qpow(v[N-1],M-2);
    for(int i=N-2;i>=0;i--){
        inv[i]=inv[i+1]*(i+1)%M;
    }
}
int C(int a,int b){
    return v[a]*inv[b]%M*inv[a-b]%M;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    init();
    cin>>n>>m;
    dp[0][0]=1;
    int s=0,mul=1;
    for(int i=1;i<=m;i++){
        int w=(2*n-i)/m+1;
        mul=mul*v[w]%M;
        for(int j=0;j<=s/2;j++){
            for(int k=0;k<=min(w,s-2*j);k++){
                int cost=C(s-2*j,k)*C(n-(s-j),w-k)%M;
                dp[i][j+k]=(dp[i][j+k]+dp[i-1][j]*cost)%M;
            }
        }
        s+=w;
    }
    int ans=dp[m][n]*mul%M*qpow(2,n)%M;
    cout<<ans;
}