大家好，又见面了，我是全栈君。
题目链接：传送门
题意：
n个格子排成一行。我们有m种颜色。能够给这些格子涂色，保证相邻的格子的颜色不同
问，最后恰好使用了k种颜色的方案数。
分析：
看完题目描写叙述之后立刻想到了一个公式 ：C(m,k)*k*(k-1)^(n-1),可是细致分析了一下
这个公式的含义是相邻的格子颜色不同，使用的颜色总数小于等于k的方案数,可是这个
公式能够帮忙我们衍生出来以下的公式。C(k,x)*x*(x-1)^(n-1),这个公式的含义是在这
k种颜色中再选出来x种使得相邻的格子不同色最后的颜色数小于等于x,然后每个集合
都有交们我们能够考虑用容斥来搞一下。
设 S = F[x]=C(k,x)*x*(x-1)^(n-1);
ans = C(m,k) * sigma{ (-1)^(k-i) * C(k,i) * i *(i – 1)^(n-1)} (1 <= i <= k)
代码例如以下：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int maxn = 1e6+10;
LL n,m,k;
LL c[maxn],inv[maxn];
LL quick_mod(LL a,LL b){
LL ans=1;
while(b){
if(b&1) ans=ans*a%mod;
b>>=1;
a=a*a%mod;
}
return ans ;
}
inline LL get_inverse(LL x){ //(a/b) % c = a*inv[b] %c if(c is a prime number) inv[b] = (b^(c-2))%c;
return quick_mod(x,mod-2);
}
void init(){//将[1,1e6+10]的逆元预处理出来
for(LL i=1;i<maxn;i++)
inv[i]=get_inverse(i);
}
void get_combine(LL n){//得到组合数
c[0]=1;
for(LL i=1;i<=k;i++){
c[i]=(c[i-1]*(n-i+1)%mod)*inv[i]%mod;
}
}
inline LL calc(LL x){// x*C(k,x)*(x-1)^(n-1)
return (c[x]*x%mod)*quick_mod(x-1,n-1)%mod;
}
int main(){
init();
int t,cas=1;
scanf("%d",&t);
while(t--){
scanf("%lld%lld%lld",&n,&m,&k);
get_combine(m);
LL ans = c[k],ans1=0,tag=1;
get_combine(k);
for(LL i=k;i>=1;i--){
ans1=(ans1+tag*calc(i)+mod)%mod;
tag=-tag;
}
ans=ans*ans1%mod;
printf("Case #%d: %lld\n", cas++, ans);
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116496.html原文链接：https://javaforall.net
