前言

另一道斯特林數相關的題目，然而可能更考樹形dp一些吧

題意簡介

題面鏈接

題目大意

求對于每個點$i$的$$S(i)=\sum _{j=1}^{n}dis(i,j{)}^k$$

數據范圍

$n\le 50000,k\le 150$

題解

直接上正解吧

同理這里有冪次
回到式子$$x^n=\sum _{i=0}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}{x}^{i\downarrow }$$證明
直接暴力帶入
$$\begin{array}{rl}S(i)& =\sum _{j=1}^{n}dis(i,j{)}^k\\ & =\sum _{j=1}^n\sum _{l=0}^k\left\{\begin{array}{c}k\\ l\end{array}\right\}dis(i,j{)}^{l\downarrow }\\ & =\sum _{l=0}^k\left\{\begin{array}{c}k\\ l\end{array}\right\}\sum _{j=1}^{n}dis(i,j{)}^{l\downarrow }\\ & =\sum _{l=0}^k\left\{\begin{array}{c}k\\ l\end{array}\right\}l!\sum _{j=1}^n\left(\genfrac{}{}{0ex}{}{dis(i,j)}{l}\right)\end{array}$$
我們發現求斯特林數是可以$\Theta (k^2)$做的，求階乘也很方便，是$\Theta (k)$的，現在關鍵是要求每個點，對于每個$1\le l\le k$的$$f(i)=\sum _{j=1}^n\left(\genfrac{}{}{0ex}{}{dis(i,j)}{l}\right)$$
眾所周知（就我不知），組合數有個很好的性質
$$C(n,m)=C(n?1,m?1)+C(n?1,m)$$
所以直接樹形dp（更準確的來說這里是上下dp）就好了
復雜度$\Theta (nk)$

代碼

注意：lydsy上的數據是有壓縮的，洛谷是未壓縮的，博主比較偷懶，所以代碼是未壓縮的輸入

#include<cstdio> #include<cctype> #include<algorithm> namespace fast_IO {const int IN_LEN=10000000,OUT_LEN=10000000;char ibuf[IN_LEN],obuf[OUT_LEN],*ih=ibuf+IN_LEN,*oh=obuf,*lastin=ibuf+IN_LEN,*lastout=obuf+OUT_LEN-1;inline char getchar_(){return (ih==lastin)&&(lastin=(ih=ibuf)+fread(ibuf,1,IN_LEN,stdin),ih==lastin)?EOF:*ih++;}inline void putchar_(const char x){if(oh==lastout)fwrite(obuf,1,oh-obuf,stdout),oh=obuf;*oh++=x;}inline void flush(){fwrite(obuf,1,oh-obuf,stdout);} } using namespace fast_IO; #define getchar() getchar_() #define putchar(x) putchar_((x)) #define rg register typedef long long LL; template <typename T> inline T max(const T a,const T b){return a>b?a:b;} template <typename T> inline T min(const T a,const T b){return a<b?a:b;} template <typename T> inline void mind(T&a,const T b){a=a<b?a:b;} template <typename T> inline void maxd(T&a,const T b){a=a>b?a:b;} template <typename T> inline T abs(const T a){return a>0?a:-a;} template <typename T> inline void swap(T&a,T&b){T c=a;a=b;b=c;} template <typename T> inline T gcd(const T a,const T b){if(!b)return a;return gcd(b,a%b);} template <typename T> inline T lcm(const T a,const T b){return a/gcd(a,b)*b;} template <typename T> inline T square(const T x){return x*x;}; template <typename T> inline void read(T&x) {char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x; } template <typename T> inline void printe(const T x) {if(x>=10)printe(x/10);putchar(x%10+'0'); } template <typename T> inline void print(const T x) {if(x<0)putchar('-'),printe(-x);else printe(x); } const int mod=10007; const int maxn=50001,maxm=100001; int n,k; int S[151][151],fac[151]; int head[maxn],nxt[maxm],tow[maxm],tmp; inline void addb(const int u,const int v) {tmp++;nxt[tmp]=head[u];head[u]=tmp;tow[tmp]=v; } int f[maxn][151]; void dfs1(const int u,const int fa) {f[u][0]=1;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa){dfs1(v,u);f[u][0]=(f[u][0]+f[v][0])%mod;for(rg int j=1;j<=k;j++)f[u][j]=(f[u][j]+f[v][j]+f[v][j-1])%mod;}} } int z[151]; void dfs2(const int u,const int fa) {for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa){z[0]=(f[u][0]+mod-f[v][0])%mod;for(rg int j=1;j<=k;j++)z[j]=(f[u][j]+mod+mod-f[v][j]-f[v][j-1])%mod;f[v][0]=(f[v][0]+z[0])%mod;for(rg int j=1;j<=k;j++)f[v][j]=(f[v][j]+z[j]+z[j-1])%mod;dfs2(v,u);}} } int main() {read(n),read(k);S[0][0]=1;for(rg int i=1;i<=k;i++)for(rg int j=1;j<=k;j++)S[i][j]=(S[i-1][j-1]+j*S[i-1][j])%mod;fac[0]=1;for(rg int i=1;i<=k;i++)fac[i]=fac[i-1]*i%mod;for(rg int i=1;i<n;i++){int u,v;read(u),read(v);addb(u,v),addb(v,u);}dfs1(1,1);dfs2(1,1);for(rg int i=1;i<=n;i++){int ans=0;for(rg int j=0;j<=k;j++)ans=(ans+S[k][j]*fac[j]%mod*f[i][j])%mod;//print(f[i][j]);print(ans),putchar('\n');}return flush(),0; }

總結

還是蠻清新的一道推式子+樹形dp題
算是一種思路的聯系吧

總結

以上是生活随笔為你收集整理的[bzoj2159]Crash 的文明世界的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。