首页 > 代码库 > CodeForces 340E Iahub and Permutations
CodeForces 340E Iahub and Permutations
容斥原理，组合数。
找出有$cnt$个数字还有没放，那么总方案数就是$cnt!$。
总方案数里面包含了正确的和非正确的，我们需要将非正确的删去。
先删去$1$个数字$a[i]=i$的情况，发现会多删，要加回两个数字$a[i]=i$的情况，发现会多加......就是一个容斥原理的过程。
#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-6;void File(){ freopen("D:\\in.txt","r",stdin); freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){ char c = getchar(); x = 0;while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - ‘0‘; c = getchar(); }}const int maxn=2010;LL c[maxn][maxn],f[maxn];LL mod=1e9+7;int n,a[maxn],h[maxn];LL MOD(LL a){ if(a>=0) return a%mod; LL ff=(-a)/mod+1; a=a+ff*mod; return a%mod;}int main(){ for(int i=0;i<=2000;i++) c[i][0]=1; for(int i=1;i<=2000;i++) for(int j=1;j<=i;j++) c[i][j]=(c[i-1][j-1]+c[i-1][j])%mod; f[0]=1; for(int i=1;i<=2000;i++) f[i]=(LL)i*f[i-1]%mod; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]!=-1) h[a[i]]=1; } int cnt=0; for(int i=1;i<=n;i++) if(a[i]==-1) cnt++; int sum=0; for(int i=1;i<=n;i++) { if(h[i]) continue; if(a[i]!=-1) continue; sum++; } LL ans=f[cnt]; LL d=-1; for(int i=1;i<=sum;i++) { LL tmp=MOD(d*c[sum][i]*f[cnt-i]); ans=(ans+tmp)%mod; d=-d; } printf("%lld\n",ans); return 0;}
CodeForces 340E Iahub and Permutations
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。