[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 数学 , 540 阅读

    题目大意:\(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;
}
Avatar_small
Challan 280 说:
2022年8月02日 16:42

Challan 280 is a very important Income tax related form used for Income tax payment of different types. Every year people across India have to file their Income tax. Sometimes you also have to make Income tax payment of different forms such as Advance Tax payable on occasions.While it may use for self-assessment tax and the tax for regular assessments, distributed profits over a land property or rents as well. Challan 280 The government of India has now made the online TIN NSDL website a blessing for tax payers. With the help of Challan 280 or ITNS 280 you can now pay your pending taxes or dues for current or previous years as well.


登录 *


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