The 2014 ACM-ICPC Asia Xi’an Regional Contest Problem F. Color(二项式反演)

传送门

题意:长度为n的一个连续串让你染色,使得相邻位置的颜色不能一样,且串中恰好一共出现k种颜色,问若是你有m种颜色(m>=k),一共有多少种染色方法满足给定条件.

我们易推得如果仅仅是要求相邻位置的颜色不一样那么

ans=m*(m-1)^{n-1}

我们再次设对于恰好出现i种颜色的染色方法种G(i)种,那么对于易得

种颜色的染色方法有种,那么对于易得

k*(k-1)^{n-1}=\sum\nolimits_{i=0}^k\binom{k}{i}*G(i)

我们再次设

F(k)=k*(k-1)^{n-1}

那么便可以得到这样的一条等式

F(k)=\sum\nolimits_{i=0}^k\binom{k}{i}*G(i)

对于形如上式的的式子,我们都可以得到以下反演结果

G(k)=\sum\nolimits_{i=0}^k(-1)^{k-i}\binom{k}{i}*F(i)

以上都是二项式反演已知的固定反演形式,如果想要了解该等式的证明

可以参考lyf学长的证明

对于14年icpc西安区域赛的的这道题,若是已知这个结论这就是个秒A的水题了,然而今天打重现直接被这道题卡死了

问了问A了的队友,说是感觉要容斥然后猜了一下结论就A了……

emmmm…….

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long long LL;

#define inf int(0x3f3f3f3f)
#define mod ll(1e9+7)
#define eps double(1e-6)
#define pi acos(-1.0)
#define lson  root << 1
#define rson  root << 1 | 1

ll n,m,k;

ll c[1000005];

ll inv[1000005];

ll powmod(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }

    return ans;
}

void init()
{
    inv[0]=1;
    for(int i=1; i<=1000001; i++)
        inv[i]=powmod(i,mod-2);
}

void init_c()
{
    c[0]=1;
    for(int i=1; i<=k; i++)
        c[i]=c[i-1]*(k-i+1)%mod*inv[i]%mod;
}

ll C(ll n,ll m)
{
    ll ans=1;
    for(int i=1; i<=m; i++)
        ans=ans*(n-i+1)%mod*inv[i]%mod;
    return ans;
}



int main()
{
    init();
    cin.tie(0);
    cout.tie(0);
    int t;
    init();
    cin>>t;
    for(int i=1; i<=t; i++)
    {
        cin>>n>>m>>k;
        cout<<"Case #"<<i<<": ";
        init_c();
        ll ans=0;
        ll flag=-1;
        for(int i=k-1; i>=1; i--)
        {
            ans=(ans+flag*i*c[i]%mod*powmod(i-1,n-1)%mod+mod)%mod;
            flag*=-1;
        }
        ans=(ans+k*c[k]*powmod(k-1,n-1))%mod;
        ans=(ans*C(m,k)+mod)%mod;
        cout<<ans<<endl;
    }
}