CF gym 101933 K King's Colors —

题目：http://codeforces.com/gym/101933/problem/K

其实每个点的颜色只要和父亲不一样即可；

所以至多 i 种颜色就是 \( i * (i-1)^{n-1} \)，设为 \( f(i) \)，设恰好 i 种颜色为 \( g(i) \)

那么 \( f(i) = \sum\limits_{j=0}^{i} C_{i}^{j} * g(j) \)

二项式反演得到 \( g(i) = \sum\limits_{j=0}^{k} (-1)^{k-j} * C_{k}^{j} * f(j) \)

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

int const xn=,mod=1e9+;

int n,k,f[xn],c[xn][xn];

int upt(int x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

ll pw(ll a,int b){ll ret=; for(;b;b>>=,a=a*a%mod)if(b&)ret=ret*a%mod; return ret;}

void init()

{

  for(int i=;i<=k;i++)c[i][]=;

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

    for(int j=;j<=i;j++)

      c[i][j]=upt(c[i-][j]+c[i-][j-]);

}

int main()

{

  n=rd(); k=rd(); init();

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

  for(int i=;i<=k;i++)f[i]=(ll)i*pw(i-,n-)%mod;

  int ans=;

  for(int i=;i<=k;i++)ans=upt(ans+(ll)f[i]*c[k][i]%mod*(((k-i)&)?-:));

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

  return ;

}

巴特西

CF gym 101933 K King's Colors —— 二项式反演

最新文章

热门文章