AtCoder Beginner Contest 214 G. Three Permutations（组合数学容斥背包二项式反演）

本文介绍: 剩下n-i个随便选（可能冲突），乘以n-i的阶乘，转化成至少冲突i次的方案数。1. 如果选了（1，n），对应长为n-2的链上选k-1对匹配的方案，在新环上：则认为是在长度为2*n的环上，选择一对相邻的点两两匹配，剩下的随便选，转化成至少冲突k次的方案数，利用二项式反演解决。2. 如果没选（1，n），对应长为n的链选k对匹配的方案，暴力合并背包，得到恰好选了i个冲突的点的方案数，由于原来长为n的环变为新的长为2n的环，考虑容斥，算恰好冲突的k次的方案数，对于环来说，一个长为n的环，

给定长为n(n<=3e3)的排列p和排列q，

求满足以下限制条件的排列r的方案数，答案对1e9+7取模

限制条件：对于任意i∈[1,n]，都有ri不等于pi，且ri不等于qi

https://www.cnblogs.com/ak-dream/p/AK_Dream123.html

感觉思路来源写的挺详细的，复述一遍

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll modpow(ll x,ll n,ll mod){ll res=1;for(;n;n>>=1,x=x*x%mod)if(n&1)res=res*x%mod;return res;}
const int N=3e3+10,M=6e3+10,mod=1e9+7;
int n,k,Finv[M],fac[M],inv[M];
int p[N],v,dp[N],c,ans;//dp[i][j]表示前i个环冲突了j对的方案数,滚掉第一维
vector<int>e[N];
bool vis[N];
void dfs(int u){
    if(vis[u])return;
    vis[u]=1;
    c++;
    for(auto &v:e[u]){
        if(vis[v])continue;
        dfs(v);
    }
}
void init(int n){
    inv[1]=1;
    for(int i=2;i<=n;++i)inv[i]=(1ll*(mod-mod/i)*inv[mod%i])%mod;
    fac[0]=Finv[0]=1;
    for(int i=1;i<=n;++i)fac[i]=1ll*fac[i-1]*i%mod,Finv[i]=1ll*Finv[i-1]*inv[i]%mod;
}
int C(int n,int m){
    if(m<0||m>n)return 0;
    return 1ll*fac[n]*Finv[n-m]%mod*Finv[m]%mod;
}
int f(int n,int k){ // 长为n的环，出现k个冲突的方案数
    if(n==1)return 1;
    int m=2*n;// 把环上每条边也看成是一个点 2n个点里选k对相邻点的匹配的方案数
    return (C(m-k,k)+C(m-k-1,k-1))%mod;
}
int main(){
    init(M-5);
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&p[i]);
    }
    for(int i=1;i<=n;++i){
        scanf("%d",&v);
        e[p[i]].push_back(v);
        e[v].push_back(p[i]);
    }
    dp[0]=1;
    for(int i=1;i<=n;++i){
        if(vis[i])continue;
        c=0;
        dfs(i);
        //printf("c:%dn",c);
        for(int j=n;j>=1;--j){
            for(int k=1;k<=min(j,c);++k){
                dp[j]=(dp[j]+1ll*f(c,k)*dp[j-k]%mod)%mod;
            }
        }
    }
    // for(int i=1;i<=n;++i){
    //     printf("i:%d dp:%dn",i,dp[i]);
    // }
    for(int i=0;i<=n;++i){
        int sg=(i&1)?-1:1;
        ans=(ans+1ll*sg*dp[i]*fac[n-i]%mod)%mod;
        ans=(ans+mod)%mod;
    }
    printf("%dn",ans);
    return 0;
}

显示所有内容

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。