【Codeforces961G】Partitions

Author Avatar
q234rty 4月 05, 2018

组合数与Stirling数。

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

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

\newcommand{\stirl}[2]{\genfrac{\{}{\}}{0pt}{}{ #1}{ #2}} ans= \left (\sum_i a_i \right) \times \sum_i i\binom{n-1}{i-1}\stirl{n-i}{k-1}

那么问题是如何求

\sum_i i\binom{n-1}{i-1}\stirl{n-i}{k-1}

问题是，据我所知并没有很好的快速对于每个 i 求出 \genfrac{\{}{\}}{0pt}{}{i}{n} 的方法。那怎么办办呢？只能推式子咯。

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

\stirl{n+1}{m+1}=\sum_i \binom{n}{i}\stirl{i}{m}

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

\newcommand{\stirl}[2]{\genfrac{\{}{\}}{0pt}{}{ #1}{ #2}} \begin{aligned} \sum_i i\binom{n-1}{i-1}\stirl{n-i}{k-1}&=\sum_i i\binom{n-1}{n-i}\stirl{n-i}{k-1}\\ &=\sum_i (n-i)\binom{n-1}{i}\stirl{i}{k-1}\\ &=n\sum_i \binom{n-1}{i}\stirl{i}{k-1} - \sum_i i\binom{n-1}{i}\stirl{i}{k-1}\\ &=n\stirl{n}{k} - \sum_i i\binom{n-1}{i}\stirl{i}{k-1} \end{aligned}

注意到 i\binom{n}{i}=n\binom{n-1}{i-1} ， \binom{n}{i}=\binom{n-1}{i}+\binom{n-1}{i-1} ：

\newcommand{\stirl}[2]{\genfrac{\{}{\}}{0pt}{}{ #1}{ #2}} \begin{aligned} \sum_i i\binom{n-1}{i}\stirl{i}{k-1}&=(n-1)\sum_i\binom{n-2}{i-1}\stirl{i}{k-1}\\ &=(n-1)\sum_i\left (\binom{n-1}{i} -\binom{n-2}{i}\right)\stirl{i}{k-1}\\ &=(n-1)\left(\sum_i\binom{n-1}{i}\stirl{i}{k-1}-\sum_i\binom{n-2}{i}\stirl{i}{k-1}\right)\\ &=(n-1)\left(\stirl{n}{k}-\stirl{n-1}{k}\right)\\ \end{aligned}

于是：

\newcommand{\stirl}[2]{\genfrac{\{}{\}}{0pt}{}{ #1}{ #2}} \begin{aligned} \sum_i i\binom{n-1}{i-1}\stirl{n-i}{k-1}&=n\stirl{n}{k} - (n-1)\left(\stirl{n}{k}-\stirl{n-1}{k}\right)\\ &=\stirl{n}{k}+(n-1)\stirl{n-1}{k} \end{aligned}

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

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

\newcommand{\stirl}[2]{\genfrac{\{}{\}}{0pt}{}{ #1}{ #2}} k!\stirl{n}{k}=\sum_i i^n \binom{k}{i}(-1)^{k-i}

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

总时间复杂度 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://www.q234rty.top/2018/04/05/cf961g/

隐藏