[2016-2017 ACM-ICPC CHINA-Final][GYM 101194 H] Great Cells
[Codeforces Round #467 (Div. 1)][Codeforces 936C] Lock Puzzle

[ICM Technex 2018 and Codeforces Round #463][Codeforces 932E] Team Work

Zarxdy34 posted @ 2018年2月16日 17:21 in Codeforces with tags DP 数学 , 129 阅读

    题目大意:\(1 \leq n \leq 10^9, 1 \leq k \leq 1000 \),求\[ \sum_{i=1}^n{C_n^i \cdot i^k}\]

    题解:这题直接强推公式会很困难,但是如果能注意到这一点的话会很好做:设\(F(k) = \sum_{i=1}^n{i^k C_n^i x^i}\),那么有\(F'(k) = \sum_{i=1}^n{i^{k+1} C_n^i x^{i-1}}\),然后可以推出\(xF'(k) = \sum_{i=1}^n{i^{k+1} C_n^i x^i}\),取\(x=1\),就是我们所求的东西。

    构造出生成函数,然后一项项求导就可以从\(F(k)\)得到\(F(k+1)\)。初始时有\(F(1) = nx(1+x)^{n-1}\)。由于最多只会产生\(k\)项(每一项的形式为\(a_i x^i (1+x)^{n-i}\),求导后为\(i \cdot a_i x^{i-1} (1+x)^{n-i} + (n-i) \cdot a_i x^i (1+x)^{n-i-1}\)),所以时间复杂度是\(O(k^2)\)的。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=5010;
const int mo=1e9+7;

int Pow(int x,int p)
{
	long long xx=x,res=1;
	while (p)
	{
		if (p&1) (res*=xx)%=mo;
		(xx*=xx)%=mo;
		p>>=1;
	}
	return res;
}

int add(int x,int y) {return (x+y)%mo;}
int mul(int x,int y) {return ((long long)x*y)%mo;}

int f[maxn][maxn];
int n,k,ans;

int main()
{
	scanf("%d%d",&n,&k);
	f[1][1]=n;
	for (int i=2;i<=k;i++)
	for (int j=1;j<=min(i,n);j++)
		f[i][j]=add(mul(f[i-1][j],j),mul(f[i-1][j-1],n-j+1));
	for (int i=min(k,n),k2=Pow(2,n-i);i>=1;i--)
		ans=add(ans,mul(f[k][i],k2)),k2=mul(k2,2);
	printf("%d\n",ans);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter