题目
给定长为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:%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;
}原文地址:https://blog.csdn.net/Code92007/article/details/135734136
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.7code.cn/show_59852.html
如若内容造成侵权/违法违规/事实不符，请联系代码007邮箱：suwngjj01@126.com进行投诉反馈，一经查实，立即删除！
