• 周二. 11月 29th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[学习笔记]二项式反演

admin

11月 28, 2021
  • 例题:[King’s Colors][https://vjudge.net/problem/Kattis-kingscolors]

    • 题意:n个点的树,用恰好k种颜色染色,并且要求相邻两个点不同。

    • 这题可以发现就是组合数学题,跟树的形状一点关系都没有。求最多用k种颜色染色的合法方案很容易:

      [f(n)=k(k-1)^{n-1}
      ]

    • 易得,令(g(k))为恰好(k)种颜色的方案数

      [f(k)=sum_{i=2}^{k}inom{k}{i}g(k)
      ]

    • 答案要求(g( n )​) 这要用到二项式反演

  • 二项式反演公式:

    [a_n=sum_{k=0}^{n}inom{n}{k}b_kLeftrightarrow b_n=sum_{k=0}^{n}(-1)^{n-k}inom{n}{k}a_k
    ]

    证明:略

  • 例题公式:

    [g(k)=sum_{i=2}^{k}(-1)^{k-i}inom{k}{i}f(i)
    ]

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod = 1e9+7;
const int maxn = 3000;
ll fac[maxn],inv[maxn];
ll qpow(ll x,ll n){
    ll res=1;
    while(n){
        if(n&1) res=x*res%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
ll c(ll n,ll m){
    return fac[n]*inv[n-m]%mod*inv[m]%mod;
}
void init(){
    fac[0]=1;
    for(ll i=1;i<maxn;++i) fac[i]=fac[i-1]*i%mod;
    inv[maxn-1]=qpow(fac[maxn-1],mod-2);
    for(ll i=maxn-2;i>=0;--i){
        inv[i]=inv[i+1]*(i+1ll)%mod;
    }
}
int main() {
    ll n,k;
    ll ans=0;
    init();
    scanf("%lld%lld",&n,&k);
    for(int i=1,x;i<n;++i) scanf("%d",&x);
    for(ll i=2;i<=k;++i){
        if((k-i)%2==0){
            ans=(ans+c(k,i)*i%mod*qpow(i-1,n-1)%mod)%mod;
        }else{
            ans=(ans-c(k,i)*i%mod*qpow(i-1,n-1)%mod+mod)%mod;
        }
    }
    printf("%lld
",ans);
    return 0;
}

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注