首页 > 代码库 > codeforces 100548F （西安现场赛F题）:容斥原理
codeforces 100548F （西安现场赛F题）:容斥原理
题目大意：
对n个排成一排的物品涂色，有m种颜色可选。
要求相邻的物品颜色不相同，且总共恰好有K种颜色，问所有可行的方案数
分析：
从m种颜色中选出k种，有c(m,k)种方法，那么我们只用考虑 k种颜色的涂法即可
显然第一个物品有k种涂法，后面的因为不能跟前面的相同都只有k-1种涂法
因此容易想到一个公式：k*(k-1)^(n-1)
但是这个公式算的是 不超过k种颜色的涂法，题目要求必须k种，怎么办呢？
先考虑一个简化版的问题：
用而且用完5种颜色涂不相关的五个物品的方案数
用阶乘的方法可以算出 ans=120，换一种思路呢想一想这个问题，容易想到
ans（取五种颜色）=5^5（取不大于5种颜色）-c(5,4)*4^5（取不大于4种颜色）
可是一算发现ans竟然小于0了，这是怎么回事呢？容易发现其实取小于四种颜色的方案被减重复了
于是想到需要容斥
ans=c(5,5)*5^5-c(5,4)*4^5+c(5,3)*3^5-c(5,2)*2^5+c(5,1)*1^5 =120
这个问题解决了。原问题也就差不多了。。
代码：
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;const long long mod=1000000007;const long long ny=500000004;long long n,m,k;long long cm[1000010];long long cn[1000010];long long ck[1000010];long long inv[1000010];long long mo(long long x){ while(x<0) x+=mod; return x%mod;}long long exgcd(long long a,long long b,long long &x,long long &y){ if(a==0&&b==0) return -1; if(b==0){x=1;y=0;return a;} long long d=exgcd(b,a%b,y,x); y-=a/b*x; return d;}long long Inv(long long a,long long n){ long long x,y; long long d=exgcd(a,n,x,y); if(d==1) return (x%n+n)%n; else return -1;}long long quickmod(long long a,long long b,long long m) //a^b%m{ long long res=1; while(b) { if(b&1) res=res*a%mod; b>>=1; a=a*a%mod; } return res;}void ini(){ cn[0]=cm[0]=1; memset(cm,0,sizeof(cm)); cm[0]=1; int tmp=min(m/2,k); for(int i=1;i<=tmp;i++) { cm[i]=(cm[i-1]*(m+1-i)%mod*inv[i])%mod; } if(cm[k]==0) cm[k]=cm[m-k]; ck[0]=ck[k]=1; for(int i=1;i<=k/2;i++) { ck[i]=(ck[i-1]*(k+1-i)%mod*inv[i])%mod; ck[k-i]=ck[i]; }}int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); inv[1]=1; for(int i=2;i<=1000000;i++) { inv[i]=Inv(i,mod); } int t; scanf("%d",&t); int cas=0; while(t--) { cas++; scanf("%I64d%I64d %I64d",&n,&m,&k); ini(); long long ans=0; long long p=1; for(int i=k;i>=1;i--) { ans=(ans+p*((ck[k-i])*i%mod*quickmod(i-1,n-1,mod)%mod)+mod)%mod; p=-p; } ans=(ans*cm[k])%mod; printf("Case #%d:%c%I64d\n",cas,‘ ‘,ans); } return 0;}
codeforces 100548F （西安现场赛F题）:容斥原理
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。