第二类斯特林数有一个公式: x k = ∑ i = 0 k S ( k , i ) i ! ( x i ) x^k=sum_{i=0}^kS(k,i)i!{xchoose i} xk=∑i=0kS(k,i)i!(ix),现在终于记住了,勉强能用了。
我们先把答案用这个公式转换一下:
S
(
u
)
=
∑
v
=
1
n
d
i
s
t
(
u
,
v
)
k
=
∑
v
=
1
n
∑
i
=
0
k
S
(
k
,
i
)
i
!
(
d
i
s
t
(
u
,
v
)
i
)
=
∑
i
=
0
k
S
(
k
,
i
)
i
!
∑
v
=
1
n
(
d
i
s
t
(
u
,
v
)
i
)
S(u)=sum_{v=1}^n dist(u,v)^k\ =sum_{v=1}^nsum_{i=0}^kS(k,i)i!{dist(u,v)choose i}\ =sum_{i=0}^kS(k,i)i!sum_{v=1}^n{dist(u,v)choose i}
S(u)=v=1∑ndist(u,v)k=v=1∑ni=0∑kS(k,i)i!(idist(u,v))=i=0∑kS(k,i)i!v=1∑n(idist(u,v))
我们设
f
(
x
,
i
)
=
∑
v
在
x
的
子
树
内
(
d
i
s
t
(
x
,
v
)
i
)
f(x,i)=sum_{v在x的子树内}{dist(x,v)choose i}
f(x,i)=∑v在x的子树内(idist(x,v)),我们知道
(
n
m
)
=
(
n
−
1
m
)
+
(
n
−
1
m
−
1
)
{nchoose m}={n-1choose m}+{n-1choose m-1}
(mn)=(mn−1)+(m−1n−1),所以
f
(
x
,
i
)
=
∑
v
在
x
的
子
树
内
(
d
i
s
t
(
x
,
v
)
−
1
i
)
+
(
d
i
s
t
(
x
,
v
)
−
1
i
−
1
)
=
∑
(
x
,
v
)
∈
E
f
(
v
,
i
)
+
f
(
v
,
i
−
1
)
f(x,i)=sum_{v在x的子树内}{dist(x,v)-1choose i}+{dist(x,v)-1choose i-1}\ =sum_{(x,v)in E}f(v,i)+f(v,i-1)
f(x,i)=v在x的子树内∑(idist(x,v)−1)+(i−1dist(x,v)−1)=(x,v)∈E∑f(v,i)+f(v,i−1)
直接树形DP转移。
由于我们要求的是每个点为根时的DP值,所以再做一次换根DP即可。
时间复杂度 O ( n k ) O(nk) O(nk)。
代码#include//JZM yyds!! #define ll long long #define uns unsigned #define IF (it->first) #define IS (it->second) #define END putchar('n') using namespace std; const int MAXN=50005; const ll INF=1e18; inline ll read(){ ll x=0;bool 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^48),s=getchar(); return f?x:-x; } int ptf[30],lpt; inline void print(ll x,char c='n'){ if(x<0)putchar('-'),x=-x; ptf[lpt=1]=x%10; while(x>9)x/=10,ptf[++lpt]=x%10; while(lpt)putchar(ptf[lpt--]^48); if(c>0)putchar(c); } inline ll lowbit(ll x){return x&-x;} const ll MOD=10007; struct edge{ int v,to;edge(){} edge(int V,int T){v=V,to=T;} }e[MAXN<<1]; int EN,G[MAXN]; inline void addedge(int u,int v){ e[++EN]=edge(v,G[u]),G[u]=EN; e[++EN]=edge(u,G[v]),G[v]=EN; } int n,k; ll fac[MAXN],S[155][155],f[MAXN][155],as[MAXN]; inline void ad(ll&a,ll b){a+=b;if(a>=MOD)a-=MOD;} inline void dfs1(int x,int fa){ f[x][0]=1; for(int i=G[x];i;i=e[i].to){ int v=e[i].v; if(v==fa)continue; dfs1(v,x); ad(f[x][0],f[v][0]); for(int j=1;j<=k;j++) ad(f[x][j],f[v][j]),ad(f[x][j],f[v][j-1]); } } inline void dfs2(int x,int fa){ for(int i=0;i<=k;i++) ad(as[x],S[k][i]*fac[i]%MOD*f[x][i]%MOD); for(int i=G[x];i;i=e[i].to){ int v=e[i].v; if(v==fa)continue; ad(f[x][0],MOD-f[v][0]); for(int j=1;j<=k;j++) ad(f[x][j],MOD-f[v][j]),ad(f[x][j],MOD-f[v][j-1]); ad(f[v][0],f[x][0]); for(int j=1;j<=k;j++) ad(f[v][j],f[x][j]),ad(f[v][j],f[x][j-1]); dfs2(v,x); ad(f[v][0],MOD-f[x][0]); for(int j=1;j<=k;j++) ad(f[v][j],MOD-f[x][j]),ad(f[v][j],MOD-f[x][j-1]); ad(f[x][0],f[v][0]); for(int j=1;j<=k;j++) ad(f[x][j],f[v][j]),ad(f[x][j],f[v][j-1]); } } signed main() { n=read(),k=read(); S[0][0]=1,fac[0]=1; for(int i=1;i<=k;i++){ fac[i]=fac[i-1]*i%MOD; for(int j=1;j<=i;j++) S[i][j]=(S[i-1][j]*j+S[i-1][j-1])%MOD; } for(int i=1;i 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)