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

题目

给定长为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

题解

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

考虑容斥，算恰好冲突的k次的方案数，

剩下的随便选，转化成至少冲突k次的方案数，利用二项式反演解决

1. 先p[i]和q[i]之间连边建图，转化成若干个环和孤立点

2. 对于孤立点，想冲突只能选和孤立点相同的值

对于环来说，一个长为n的环，

如果需要选k条边，每条边需要钦定一个端点， 并且k条边之间钦定的端点不能相同

变边为点：把要选的边也看成是一个端点，并和其原来左右相连的两个端点各连一条边

这样仍然是一个环，

原来的操作：选一条边并钦定一个相连的点，

在新环上：则认为是在长度为2*n的环上，选择一对相邻的点两两匹配，

长为n的环上选k对相邻点的方案数

?刚才的博弈题也用到了这个计数技巧，

Codeforces Round #733 (Div. 1 + Div. 2) F. Omkar and Akmar(组合数学+博弈思维题)-CSDN博客

经典问题，分选不选（1,n）考虑，拆环，

1. 如果选了（1，n），对应长为n-2的链上选k-1对匹配的方案，

2. 如果没选（1，n），对应长为n的链选k对匹配的方案，

由于原来长为n的环变为新的长为2n的环，

所以原来大小为n的环上选出k个的方案，为

需要额外判断一下自环的情况，自环时冲突只有一种方案

对于若干个环，暴力合并背包，得到恰好选了i个冲突的点的方案数，

剩下n-i个随便选（可能冲突），乘以n-i的阶乘，转化成至少冲突i次的方案数

容斥即可，即对应二项式反演，有：

注意中间会用到2*n，所以组合数初始化到6e3

代码

#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:%d\n",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:%d\n",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("%d\n",ans);
    return 0;
}