【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

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXSIZE=10000020;
  5. const int mod=1000000007;
  6. int bufpos;
  7. char buf[MAXSIZE];
  8. #define NEG 0
  9. void init(){
  10. 	#ifdef LOCAL
  11. 		freopen("961G.txt","r",stdin);
  12. 	#endif
  13. 	buf[fread(buf,1,MAXSIZE,stdin)]='\0';
  14. 	bufpos=0;
  15. }
  16. #if NEG
  17. int readint(){
  18. 	bool isneg;
  19. 	int val=0;
  20. 	for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
  21. 	bufpos+=(isneg=buf[bufpos]=='-');
  22. 	for(;isdigit(buf[bufpos]);bufpos++)
  23. 		val=val*10+buf[bufpos]-'0';
  24. 	return isneg?-val:val;
  25. }
  26. #else
  27. int readint(){
  28. 	int val=0;
  29. 	for(;!isdigit(buf[bufpos]);bufpos++);
  30. 	for(;isdigit(buf[bufpos]);bufpos++)
  31. 		val=val*10+buf[bufpos]-'0';
  32. 	return val;
  33. }
  34. #endif
  35. char readchar(){
  36. 	for(;isspace(buf[bufpos]);bufpos++);
  37. 	return buf[bufpos++];
  38. }
  39. int readstr(char* s){
  40. 	int cur=0;
  41. 	for(;isspace(buf[bufpos]);bufpos++);
  42. 	for(;!isspace(buf[bufpos]);bufpos++)
  43. 		s[cur++]=buf[bufpos];
  44. 	s[cur]='\0';
  45. 	return cur;
  46. }
  47. ll power(ll x,ll y){
  48. 	x%=mod;
  49. 	ll ans=1;
  50. 	while(y){
  51. 		if (y&1)
  52. 			ans=ans*x%mod;
  53. 		x=x*x%mod;
  54. 		y>>=1;
  55. 	}
  56. 	return ans;
  57. }
  58. ll fac[200002],invf[200002];
  59. ll c(int n,int m){
  60. 	if (n<m)
  61. 		return 0;
  62. 	return fac[n]*invf[m]%mod*invf[n-m]%mod;
  63. }
  64. ll s(int n,int m){
  65. 	ll ans=0;
  66. 	for(int i=1;i<=m;i++){
  67. 		ll now=power(i,n)*c(m,i)%mod;
  68. 		if ((m-i)%2)
  69. 			ans-=now;
  70. 		else ans+=now;
  71. 	}
  72. 	return ans%mod*invf[m]%mod;
  73. }
  74. int main(){
  75. 	init();
  76. 	int n=readint(),k=readint();
  77. 	ll sum=0;
  78. 	for(int i=1;i<=n;i++)
  79. 		sum+=readint();
  80. 	sum%=mod;
  81. 	fac[0]=1;
  82. 	for(int i=1;i<=n;i++)
  83. 		fac[i]=fac[i-1]*i%mod;
  84. 	invf[n]=power(fac[n],mod-2);
  85. 	for(int i=n;i;i--)
  86. 		invf[i-1]=invf[i]*i%mod;
  87. 	ll ans=(s(n,k)+(n-1)*s(n-1,k))%mod*sum%mod;
  88. 	printf("%lld",(ans+mod)%mod);
  89. }

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/04/05/cf961g/

隐藏