首页 > 代码库 > Color
Color
题意:
$n$个球相邻排成一排,现在用$m$种颜色给球染色,要求相邻球颜色不同,且恰好出现了$K$。
求满足条件的染色方案的个数。
解法:
只要求出用$K$种颜色给$n$个球染色,并且相邻球颜色不同的方案数即可。
考虑容斥,$K$种颜色全都出现的方案数,可以用$r$种颜色没有出现 容斥得到。
$$F(n,K) = \sum_{r=0}^{K-1} {C_K^r (-1)^{r} (K-r-1)^{n-1} (K-r)}$$
从而有 $ans = C_m^K F(n,K)$
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 #define LL long long 6 #define P 1000000007LL 7 #define N 1000010 8 9 using namespace std; 10 11 int n,m,K; 12 LL inv[N]; 13 14 LL qpow(LL x,int n) 15 { 16 LL ans=1; 17 for(;n;n>>=1,x=x*x%P) if(n&1) ans=ans*x%P; 18 return ans; 19 } 20 21 int main() 22 { 23 int T,Te=0; 24 scanf("%d",&T); 25 for(int i=1;i<N;i++) inv[i]=qpow(i,P-2); 26 while(T--) 27 { 28 scanf("%d%d%d",&n,&m,&K); 29 int tp=1; 30 LL CK_r = K,ans=0; 31 for(int r=1;r<=K;r++) 32 { 33 LL tmp = tp * CK_r%P * qpow(r-1,n-1)%P * r%P; 34 ans += tmp; 35 if(ans>=P) ans-=P; 36 if(r<K) CK_r = CK_r * inv[r+1]%P * (K-r)%P; 37 tp = P-tp; 38 } 39 if(tp==1) ans = P-ans; 40 LL Cm_K = 1; 41 for(int i=1;i<=K;i++) 42 Cm_K = Cm_K * inv[i]%P * (m-i+1LL)%P; 43 ans = Cm_K*ans%P; 44 printf("Case #%d: %d\n",++Te,(int)ans); 45 } 46 }
Color
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。