题解 CF932E 【Team Work】

你打野 · 2019-01-14 22:00:54 · 题解

献上官方题解神奇的数学结论：

将这个式子左右两边重复k次以下操作：

先求导再乘x,

最后令x=1,等式右边就是所求答案。

那么怎样求等式左边呢？

设dp[a][b][c]表示xb(1 + x)c ，求导乘x的操作a次之后的结果。则利用数学知识求导(高中数学),可以得到

由此得到dp关系式

dp[a][b][c] = b  dp[a - 1][b][c] + c  dp[a - 1][b + 1][c - 1]

因为b+c是定值，所以可以将dp的状态压缩成二维，记忆化搜索得到答案。边界条件为k=0,a=0或b=0.

#include<cstdio>
#include<cstring>
#include<cmath>
typedef long long ll;
typedef long double ld;
typedef double db;
const int maxn=5005,inf=0x3f3f3f3f;  
const ll llinf=0x3f3f3f3f3f3f3f3f,mod=1e9+7;   
const ld pi=acos(-1.0L);
ll dp[maxn][maxn]; 
ll fastpow(ll base,ll index) {  
ll sum=base,ans=1,i=index;  
while(i){  
if(i%2)ans=(ans*sum)%mod;  
sum*=sum;sum=sum%mod;i/=2; }  
return ans;}
ll solve(ll k,ll n,ll a,ll b) {
if(dp[k][a]!=-1)return dp[k][a];
if(k==0)return dp[k][a]=fastpow(2,b);
return dp[k][a]=((b==0?0LL:b*solve(k-1,n,a+1,b-1)%mod)+(a==0?0LL:a*solve(k-1,n,a,b)%mod))%mod;}
main() {ll n,k;
scanf("%I64d%I64d",&n,&k);
memset(dp,-1,sizeof(dp));
ll ans=solve(k,n,0,n);
printf("%I64d\n",ans);}