这是道好题啊，以前没遇到过可以这么搞的。
求:
∑i=1n(ni)ik ∑ i = 1 n ( n i ) i k题解： (1+x)n=∑i=1n(ni) ( 1 + x ) n = ∑ i = 1 n ( n i ) 然后不停对他求导，再乘上 x x 。 这样做kk次最后把 x=1 x = 1 带进去就可以直接算了。
#include <bits/stdc++.h> typedef long long LL; using namespace std; const int mod=1e9+7,N=5005; int n,k,dp[N][N]; inline int mul(int x,int y) {return (LL)x*y%mod;} inline void add(int &x,int y) {x=(x+y>=mod)?x+y-mod:x+y;} inline int power(int a,int b) { int rs=1; for(;b;b>>=1,a=(LL)a*a%mod) if(b&1) rs=(LL)rs*a%mod; return rs; } int main() { cin>>n>>k; dp[0][0]=1; for(int i=1;i<=k;i++) for(int j=1;j<=k;j++) { add(dp[i][j],mul(dp[i-1][j],j)); add(dp[i][j],mul(dp[i-1][j-1],n-j+1)); } int ans=0; for(int j=0;j<=k && j<=n;j++) add(ans,mul(dp[k][j],power(2,n-j))); printf("%d\n",ans); }就是在子树维护凸包斜率优化 DP D P ，合并凸包时启发式合并时间复杂度 O(nlog2n) O ( n log 2 n ) （用公切线可以做到 O(nlogn) O ( n log n ) ，不过有点难写）
（用 long long 叉乘会溢出，注意转化为double）
啊，原来写动态凸包还有用1个set的方法，算是学到了。
#include <bits/stdc++.h> typedef long double LD; typedef long long LL; using namespace std; const LD eps=0; inline int sgn(LD x) {return (x>eps)-(x<-eps);} inline int rd() { char ch=getchar(); int i=0,f=1; while(!isdigit(ch)) {if(ch=='-')f=-1; ch=getchar();} while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=getchar();} return i*f; } inline void W(LL x) { static int buf[50]; if(!x) {putchar('0'); return;} if(x<0) {putchar('-'); x=-x;} while(x) {buf[++buf[0]]=x%10; x/=10;} while(buf[0]) {putchar(buf[buf[0]--]+'0');} } const int N=1e5+50; const LD INF=1e18; bool fg=1; int n,deg[N]; LL f[N],a[N],b[N]; vector <int> edge[N]; struct P { LL x,y; LD slope; P(LL x=0,LL y=0,LD slope=0):x(x),y(y),slope(slope){} friend inline P operator -(const P &a,const P &b) {return P(a.x-b.x,a.y-b.y,0);} friend inline LD operator *(const P &a,const P &b) {return (LD)a.x*b.y-(LD)a.y*b.x;} }; struct cmp { inline bool operator ()(const P &a,const P &b) { if(fg) { if(a.x!=b.x) return a.x<b.x; return a.y<b.y; } else return sgn(a.slope-b.slope)<0; } }; typedef set<P,cmp> Set; Set *S[N]; typedef Set :: iterator it; inline it bef(it t) {return --t;} inline it nxt(it t) {return ++t;} inline LD calc_slope(P x,P y) {return (LD)(y.y-x.y)/(y.x-x.x);} inline void ins(Set &x,P p) { fg=1; int bg=0; if(!x.size()) {x.insert(p); return;} it suf=x.lower_bound(p); it pre=(suf==x.begin())?suf:bef(suf); if(x.size()!=1 && suf!=x.end() && suf!=x.begin() && ((*suf)-p)*((*pre)-p)<=0 ) return; if(suf!=x.end() && suf->x==p.x && suf->y==p.y) return; if(suf!=x.begin() && pre->x==p.x && pre->y<=p.y) return; if(suf!=x.begin()) { while(pre!=x.begin()) { if(((*pre)-p)*((*bef(pre))-p)>=0) pre=bef(pre),x.erase(nxt(pre)); else if(pre->x==p.x&&pre->y>=p.y) pre=bef(pre),x.erase(nxt(pre)); else break; } if(pre==x.begin() && pre->x==p.x && pre->y>=p.y) bg=1,x.erase(nxt(pre)); } else bg=1; while(suf!=x.end()) { if(suf!=--x.end() && ((*suf)-p)*((*nxt(suf))-p)<=0) suf=nxt(suf),x.erase(bef(suf)); else if(suf->x==p.x&&suf->y>=p.y) suf=nxt(suf),x.erase(bef(suf)); else break; } if(suf!=x.end()) { P tp=*suf; tp.slope=calc_slope(*suf,p); x.erase(suf); x.insert(tp); } if(bg) p.slope=-INF; else p.slope=calc_slope(*pre,p); x.insert(p); } inline void merge(Set *&x,Set *y) { if(x->size()<y->size()) swap(x,y); for(it i=y->begin(); i!=y->end(); ++i) ins(*x,*i); delete y; } inline LL query(Set &x,int id) { fg=0; P tp=P(0,0,-a[id]); it suf=--x.lower_bound(tp); return (LL)(a[id]*suf->x+suf->y); } inline void dfs(int x,int fa) { if(deg[x]==1 && x!=1) { ins(*S[x],P(b[x],0,-INF)); return; } for(int e=edge[x].size()-1;e>=0;e--) { int v=edge[x][e]; if(v==fa) continue; dfs(v,x); merge(S[x],S[v]); } f[x]=query(*S[x],x); ins(*S[x],P(b[x],f[x],0)); } int main() { n=rd(); for(int i=1;i<=n;i++) S[i]=new Set; for(int i=1;i<=n;i++) a[i]=rd(); for(int i=1;i<=n;i++) b[i]=rd(); for(int i=1;i<n;i++) { int x=rd(), y=rd(); edge[x].push_back(y); edge[y].push_back(x); ++deg[x]; ++deg[y]; } dfs(1,0); for(int i=1;i<=n;i++) W(f[i]),putchar(' '); }