首页 > 代码库 > Color

Color

2024-09-13 11:26:30   215人阅读

题意：

$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 }
View Code

 

Color


联系
我们