Codeforces 932E. Team Work-数学

传送门

题意：

给定n,k,求 ∑nr=1Crnrk ∑ r = 1 n C n r r k

n<=1e9,k<=5e3 n <= 1 e 9 , k <= 5 e 3

Solution:

冥思苦想数论方式……..最后GG

题解让人眼前一亮：

定义函数 f(x)=(1+x)n=∑nr=0Crnxr f ( x ) = ( 1 + x ) n = ∑ r = 0 n C n r x r

那么我们对他求一次导: f′(x)=n(1+x)n−1=∑nr=1Crnrxr−1 f ′ ( x ) = n ( 1 + x ) n − 1 = ∑ r = 1 n C n r r x r − 1

再把这个式子乘一个x: xf′(x)=nx(1+x)n−1=∑nr=1Crnrxr x f ′ ( x ) = n x ( 1 + x ) n − 1 = ∑ r = 1 n C n r r x r

然后我们发现：对于 f(x) f ( x ) ，题目所给的公式就是我们对它进行上面的操作（求导后乘x）k次后x=1的值

那么这道题现在就转化成关于 f(x) f ( x ) 的问题了

设 f[a][b][c] f [ a ] [ b ] [ c ] 是对 xb(1+x)c x b ( 1 + x ) c 做a次操作后x=1的值

那么最终的答案即为 f[k][0][n] f [ k ] [ 0 ] [ n ]

转移依据高中知识： f[a][b][c]=b∗f[a−1][b][c]+c∗f[a−1][b+1][c−1] f [ a ] [ b ] [ c ] = b ∗ f [ a − 1 ] [ b ] [ c ] + c ∗ f [ a − 1 ] [ b + 1 ] [ c − 1 ]

a=0时, f[a][b][c]=2c f [ a ] [ b ] [ c ] = 2 c

进行记忆化搜索即可

虽然状态是三维的，但是因为b+c恒等于n,所以我们的复杂度实际上是 O(k2) O ( k 2 ) 的

注意特判边界情况

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int f[5010][5010];
int n,k;
const int mod=1e9+7;
int fast_pow(int x,int a)
{
    int ans=1;
    for (;a;a>>=1,x=1ll*x*x%mod) if (a&1) ans=1ll*ans*x%mod;
    return ans;
}
int dp(int a,int b)
{
    if (b>n) return 0;
    if (f[a][b]>=0) return f[a][b];
    int c=n-b;
    if (a==0) {f[a][b]=fast_pow(2,c);return f[a][b];}
    f[a][b]=(1ll*b*dp(a-1,b)+1ll*c*dp(a-1,b+1))%mod;
    return f[a][b];
}
int main()
{
    scanf("%d%d",&n,&k);
    memset(f,-1,sizeof(f));
    printf("%d",dp(k,0));
}