Team Work
题解
数学题都贞德好讨厌呀
开始推公式。
由于当时可以直接用暴力做了，我们下面只考虑的情况。
原式
。
现在这个样子其实可以直接用斯特林数做了，但我们还是先考虑将斯特林数展开一下
原式
我们设,，也就是后面那一块。
我们考虑通过线性递推的方式处理，计算，可得，
所以，得到递推式
我们只需要线性处理出组合数与的值即可，时间复杂度，也可以用埃筛的方式线性求出。
源码
#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;
#define MAXN 5005
const double eps=1e-7;
const int INF=0x7f7f7f7f;
const LL mo=1e9+7;
const int inv2=5e8+4;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){
_T f=1;x=0;char s=getchar();
while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}
while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}
x*=f;
}
int qkpow(int a,int s){
int t=1;
while(s){
if(s&1)t=1ll*a*t%mo;
a=1ll*a*a%mo;s>>=1;
}
return t;
}
int add(int x,int y){return x+y>=mo?x+y-mo:x+y;}
int n,k,f[MAXN],c[MAXN],inv[MAXN],pw[MAXN],prime[MAXN],cntp;
void init(){
c[0]=inv[1]=pw[1]=1;c[1]=n;
for(int i=2;i<=k+1;++i){
inv[i]=1ll*(mo-mo/i)*inv[mo%i]%mo;
c[i]=1ll*c[i-1]*inv[i]%mo*(n-i+1)%mo;
if(!pw[i])prime[++cntp]=i,pw[i]=qkpow(i,k);
for(int j=1;j<=cntp&&i*prime[j]<=k;++j){
pw[i*prime[j]]=1ll*pw[i]*pw[prime[j]]%mo;
if(i%prime[j]==0)break;
}
}
}
int work1(){
int res=0;
for(int i=1;i<=n;++i)
res=add(res,1ll*c[i]*pw[i]%mo);
return res;
}
int work2(){
int mul,c2,res=0;mul=c2=f[k]=1;
for(int i=k-1;i>0;--i){
c2=1ll*c2*(n-i-1)%mo*inv[k-i]%mo;
mul=1ll*mul*(mo-inv2)%mo;
f[i]=add(1ll*c2*mul%mo,1ll*inv2*f[i+1]%mo);
}
mul=inv2;
for(int i=1;i<=k;++i){
res=add(res,1ll*pw[i]*c[i]%mo*mul%mo*f[i]%mo);
mul=1ll*mul*inv2%mo;
}
res=1ll*res*qkpow(2,n)%mo;
return res;
}
signed main(){
read(n);read(k);init();
if(n<=k+1)printf("%d\n",work1());
else printf("%d\n",work2());
return 0;
}
谢谢！！！
