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

发布时间:2024年01月21日

题目

给定长为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对匹配的方案,

C_{n-2-(k-1)}^{k-1}=C_{n-1-k}^{k-1}

2. 如果没选(1,n),对应长为n的链选k对匹配的方案,C_{n-k}^{k}

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

所以原来大小为n的环上选出k个的方案,为C_{2*n-k-1}^{k-1}+C_{2*n-k}^{k}

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

对于若干个环,O(n^2)暴力合并背包,得到恰好选了i个冲突的点的方案数,

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

容斥即可,即对应二项式反演,有:

ans=\sum_{i=0}^n(-1)^i*dp[i]*(n-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;
}

文章来源:https://blog.csdn.net/Code92007/article/details/135734136
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。