CF gym 101933 K. King's Colors(二项式反演)

传送门

##解题思路
　　首先给出的树形态没用，因为除根结点外每个点只有一个父亲，它只需要保证和父亲颜色不同即可。设$f(k)$表示至多染了$k$种颜色的方案，那么$f(k)=(k-1)^{(n-1)}*k$，而我们要求的是恰好染$k$种颜色的方案数，设其为$g(k)$，易得

\[
g(k)=\sum\limits_{i=1}^k\dbinom{k}{i}f(i)
\]

发现这个可以二项式反演

\[
g(k)=\sum\limits_{i=1}^k(-1)^{k-i}\dbinom{n}{i}f(i)
\]

然后就可以直接算了。

##代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

using namespace std;

const int N=2505;

const int MOD=1e9+7;

typedef long long LL;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return f?x:-x;

}

int n,k,f[N],ans,fac[N],inv[N];

inline int fast_pow(int x,int y){

	int ret=1;

	for(;y;y>>=1){

		if(y&1) ret=(LL)ret*x%MOD;

		x=(LL)x*x%MOD;

	}

	return ret;

}

inline int C(int x,int y){

	return (LL)fac[x]*inv[y]%MOD*inv[x-y]%MOD;

}

int main(){

	n=rd(),k=rd();int x;fac[0]=1;

	for(int i=1;i<n;i++) x=rd();

	for(int i=1;i<=k;i++) fac[i]=(LL)fac[i-1]*i%MOD;

	inv[k]=fast_pow(fac[k],MOD-2);

	for(int i=k-1;~i;i--) inv[i]=(LL)inv[i+1]*(i+1)%MOD;

	for(int i=2;i<=k;i++) f[i]=(LL)fast_pow(i-1,n-1)*i%MOD;

	for(int i=1;i<=k;i++){

		if(!((k-i)&1)) ans=ans+(LL)C(k,i)*f[i]%MOD;

		else ans=ans+(MOD-(LL)C(k,i)*f[i]%MOD);

		ans%=MOD;

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

CF gym 101933 K. King's Colors(二项式反演)

最新文章

热门文章