题目

https://codeforces.com/contest/932/problem/E

中文题面：有N(1≤N≤1e9)个不同的人，你从中选择x(x至少为1)个人去完成一个团队任务，代价为xk(1≤k≤5000)。     求所有组队方案的总代价。

关于导数四则运算：https://www.cnblogs.com/liming19680104/p/10955536.html

题解

很容易得出题目要求 ①，这里i=0不影响答案，

看到很容易想到二项式定理：②，

①式和②式很像，而②式比①式好算多了，如何把②式变为①式呢？

答案是：求导

如果把②式求导后乘以x，再求导乘以x，如此重复，变为、、···，重复k次以后就变为，由于x是我们随意取的一个数，令它等于1，②式右边最终变为，因此只要算②式左边求导结果就可得到答案

②式左边变换过程：

一次：

此时函数变为两个函数 、 相乘，根据导数四则运算中的

可以进行如下变换：

如此对形如 （  为该项系数）的每一项都可变为 ，

进行k次变换，最多产生k项，其中的项消去不算，用dp维护系数，复杂度

代码

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<cmath> #include<vector> #define ll long long #define MAXN 5005 #define MOD 1000000007ll using namespace std; inline ll read(){ ll x=0,f=1;char s=getchar(); while((s<'0'||s>'9')&&s>0){if(s=='-')f*=-1;s=getchar();} while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+s-'0';s=getchar();} return x*f; } int k; ll n,dp[MAXN],ans; inline ll ksm(ll a,ll b,ll mo){ ll res=1; for(;b;b>>=1){ if(b&1)res=res*a%mo; a=a*a%mo; } return res; } int main() { n=read(),k=read(); dp[1]=n; for(int i=2;i<=k;i++) for(int j=i;j>0;j--) dp[j]=(dp[j-1]*(n-j+1)+dp[j]*j)%MOD; for(int i=1;i<=k;i++) if(n-i>=0)ans=(ans+dp[i]*ksm(2,n-i,MOD))%MOD;//令x等于1 printf("%lld\n",ans); return 0; }