【Codeforces961G】Partitions

组合数与Stirling数。

下文所说的Stirling数均指第二类Stirling数。

首先枚举S|S|可以得到:

那么问题是如何求

问题是,据我所知并没有很好的快速对于每个ii求出 的方法。那怎么办办呢?只能推式子咯。

首先我们翻开具体数学,注意到不带容斥系数的组合数乘以Stirling数的和的公式只有下面这个:

那么就决定是你了,接下来我们来看怎么用这个化简上面那个式子。

注意到i(ni)=n(n1i1)i\binom{n}{i}=n\binom{n-1}{i-1}(ni)=(n1i)+(n1i1)\binom{n}{i}=\binom{n-1}{i}+\binom{n-1}{i-1}

于是:

那么剩下的问题是怎么计算Stirling数。

算上集合的排列顺序,容斥一波可以发现:

于是预处理阶乘就可以O(klogn)O(k \log n)计算了。

总时间复杂度O(klogn)O(k \log n)

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
const int mod=1000000007;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("961G.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
ll power(ll x,ll y){
    x%=mod;
    ll ans=1;
    while(y){
        if (y&1)
            ans=ans*x%mod;
        x=x*x%mod;
        y>>=1;
    }
    return ans;
}
ll fac[200002],invf[200002];
ll c(int n,int m){
    if (n<m)
        return 0;
    return fac[n]*invf[m]%mod*invf[n-m]%mod;
}
ll s(int n,int m){
    ll ans=0;
    for(int i=1;i<=m;i++){
        ll now=power(i,n)*c(m,i)%mod;
        if ((m-i)%2)
            ans-=now;
        else ans+=now;
    }
    return ans%mod*invf[m]%mod;
}
int main(){
    init();
    int n=readint(),k=readint();
    ll sum=0;
    for(int i=1;i<=n;i++)
        sum+=readint();
    sum%=mod;
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=fac[i-1]*i%mod;
    invf[n]=power(fac[n],mod-2);
    for(int i=n;i;i--)
        invf[i-1]=invf[i]*i%mod;
    ll ans=(s(n,k)+(n-1)*s(n-1,k))%mod*sum%mod;
    printf("%lld",(ans+mod)%mod);
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。

本文链接:https://q234rty.top/2018/04/05/cf961g/

隐藏