BZOJ.2159.Crash的文明世界(斯特林数 树形DP)

时间:2021-11-30 19:40:50

BZOJ

洛谷


挺套路但并不难的一道题

\(Description\)

给定一棵\(n\)个点的树和\(K\),边权为\(1\)。对于每个点\(x\),求\(S(x)=\sum_{i=1}^ndis(x,i)^K\)。

\(n\leq50000,\ k\leq150\)。

\(Solution\)

和其它求\(x^k\)的题一样,依旧用第二类斯特林数展开。(二项式定理依旧可以得到部分分,依旧不想看=-=)

\[\begin{aligned}S(x)&=\sum_{i=1}^ndis(x,i)^K\\&=\sum_{i=1}^n\sum_{k=0}^{dis(x,i)}S(K,k)\cdot k!\cdot \binom{dis(x,i)}{k}\\&=\sum_{i=1}^n\sum_{k=0}^KS(K,k)\cdot k!\cdot \binom{dis(x,i)}{k}\\&=\sum_{k=0}^KS(K,k)\cdot k!\cdot\sum_{i=1}^n\binom{dis(x,i)}{k}\end{aligned}
\]

考虑这个\(\sum_{i=1}^n\binom{dis(x,i)}{k}\)怎么算。用阶乘公式拆还是一样没法算,尝试用这个公式拆:\(\binom nm=\binom{n-1}m\times\binom{n-1}{m-1}\):

\[\sum_{i=1}^n\binom{dis(x,i)}{k}=\sum_{i=1}^n\binom{dis(x,i)-1}{k}+\sum_{i=1}^n\binom{dis(x,i)-1}{k-1}
\]

记\(f[x][k]=\sum_{i=1}^n\binom{dis(x,i)}{k}\),那么可以由\(x\)的相邻点\(v\)的\(f[v][k]+f[v][k-1]\)转移来(\(x\)和\(v\)与其它点的\(dis\)正好差\(1\))。

具体就是两遍树形DP,第一次自底向上求出子树内的点到\(x\)的\(dis\)的贡献,即\(f[x][i]=\sum_{v\in son[x]}f[v][i]+f[v][i-1]\);第二次从上往下更新子树外的点到\(v=son[x]\)的\(dis\)的贡献,记为\(g[v][i]=g[x][i]+g[x][i-1]+(f[x][i]-f[v][i]-f[v][i-1])+(f[x][i-1]-f[v][i-1]-f[v][i-2])\)。

然后统计一下就OK了。复杂度\(O(nk+k^2)\)。

明明取模优化的不少啊,怎么就这么慢呢=-=


//33844kb	4868ms
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
#define mod 10007
#define Mod(x) x>=mod&&(x-=mod)
#define Add(x,v) (x+=v)>=mod&&(x-=mod)
typedef long long LL;
const int N=50003,M=153; int K,Enum,H[N],nxt[N<<1],to[N<<1],f[N][M]; inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-48,c=gc());
return now;
}
inline void AE(int u,int v)
{
to[++Enum]=v, nxt[Enum]=H[u], H[u]=Enum;
to[++Enum]=u, nxt[Enum]=H[v], H[v]=Enum;
}
void DFS1(int x,int fa)
{
f[x][0]=1;//这个初始化...C(dis(x,x),0)=1?有点小懵逼=-=
int K=::K;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa)
{
DFS1(v,x), f[x][0]+=f[v][0];
for(int j=1; j<=K; ++j) f[x][j]+=f[v][j]+f[v][j-1];
}
for(int i=0; i<=K; ++i) f[x][i]%=mod;
}
void DFS2(int x,int fa)
{
static int g[N];
int K=::K;
for(int i=H[x],v; i; i=nxt[i])
if((v=to[i])!=fa)
{
g[0]=f[x][0]+mod-f[v][0];
for(int j=1; j<=K; ++j) g[j]=f[x][j]+mod-f[v][j]+mod-f[v][j-1];//g[j] = g[x][j]+f[x][j]-f[v][j]-f[v][j-1]
f[v][0]=(f[v][0]+g[0])%mod;
for(int j=1; j<=K; ++j) f[v][j]=(f[v][j]+g[j]+g[j-1])%mod;
DFS2(v,x);
}
} int main()
{
static int S[M][M];
const int n=read(),K=read(); ::K=K;
// for(int i=1; i<n; ++i) AE(read(),read());
for(int L=read(),now=read(),A=read(),B=read(),Q=read(),i=1; i<n; ++i)
now=(now*A+B)%Q, AE(i-now%(i<L?i:L),i+1); DFS1(1,1), DFS2(1,1), S[0][0]=1;
for(int i=1; i<=K; ++i)
for(int j=1; j<=i; ++j) S[i][j]=(S[i-1][j-1]+S[i-1][j]*j)%mod;
for(int x=1; x<=n; ++x)
{
LL ans=0;
for(int i=0,fac=1; i<=K; ++i) ans+=1ll*S[K][i]*fac*f[x][i]%mod, fac=fac*(i+1)%mod;
printf("%d\n",(int)(ans%mod));
} return 0;
}

BZOJ.2159.Crash的文明世界(斯特林数 树形DP)的更多相关文章

  1. 【BZOJ2159】Crash的文明世界 斯特林数&plus;树形dp

    Description Crash 小朋友最近迷上了一款游戏--文明5(Civilization V).在这个游戏中,玩家可以建立和发展自己的国家,通过外交和别的国家交流,或是通过战争征服别的国家.现 ...

  2. &lbrack;BZOJ2159&rsqb;Crash的文明世界&lpar;斯特林数&plus;树形DP&rpar;

    题意:给定一棵树,求$S(i)=\sum_{j=1}^{n}dist(i,j)^k$.题解:根据斯特林数反演得到:$n^m=\sum_{i=0}^{n}C(n,i)\times i!\times S( ...

  3. BZOJ 2159&colon; Crash 的文明世界(树形dp&plus;第二类斯特林数&plus;组合数)

    题意 给定一棵 \(n\) 个点的树和一个常数 \(k\) , 对于每个 \(i\) , 求 \[\displaystyle S(i) = \sum _{j=1} ^ {n} \mathrm{dist ...

  4. bzoj 2159 Crash 的文明世界 &amp&semi;&amp&semi; hdu 4625 JZPTREE ——第二类斯特林数&plus;树形DP

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2159 学习材料:https://blog.csdn.net/litble/article/d ...

  5. BZOJ 2159&colon; Crash 的文明世界&lpar;组合数学&plus;第二类斯特林数&plus;树形dp&rpar;

    传送门 解题思路 比较有意思的一道数学题.首先\(n*k^2\)的做法比较好想,就是维护一个\(x^i\)这种东西,然后转移的时候用二项式定理拆开转移.然后有一个比较有意思的结论就是把求\(x^i\) ...

  6. bzoj 2159 Crash 的文明世界 &amp&semi; hdu 4625 JZPTREE —— 第二类斯特林数&plus;树形DP

    题目:https://www.lydsy.com/JudgeOnline/problem.php?id=2159 使用公式:\( n^{k} = \sum\limits_{i=0}^{k} S(k,i ...

  7. bzoj 2159&colon; Crash 的文明世界

    Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 480  Solved: 234[Submit][Status][Discuss] Descripti ...

  8. &lbrack;bzoj 2159&rsqb;Crash的文明世界

    今天看到一个鬼题 心情好的时候写 [题意]求树上所有点对距离的k次方和,所有边权为1 大爷方的题解:http://tonyfang.is-programmer.com/posts/204972.htm ...

  9. 洛谷P4827 &lbrack;国家集训队&rsqb; Crash 的文明世界 &lbrack;斯特林数,组合数,DP&rsqb;

    传送门 思路 又见到这个\(k\)次方啦!按照套路,我们将它搞成斯特林数: \[ ans_x=\sum_{i=0}^k i!S(k,i)\sum_y {dis(x,y) \choose i} \] 前 ...

随机推荐

  1. hdu 4278 2012天津赛区网络赛 数学 &ast;

    8进制转为10进制 #include<cstdio> #include<iostream> #include<algorithm> #include<cstr ...

  2. 采用Service实现本地推送通知

    在android的应用层中,涉及到很多应用框架,例如:Service框架,Activity管理机制,Broadcast机制,对话框框架,标题栏框架,状态栏框架,通知机制,ActionBar框架等等. ...

  3. 使用JS开发桌面端应用程序NW&period;js-3-开发问题小记

    前言 因为我们的项目是2C的,而XP系统是最大的用户量占比,所以只能使用nw开发而不能用Electron,本文谨记开发nw过程中遇到的各种问题以及解决方案. nw.Window.open打开新窗口不能 ...

  4. 查找IDEA 项目中的依赖包存放在&period;m2位置

    原因:在maven项目pom.xml中添加依赖,可能由于网络不好,下载不完全,导致再次下载一直报错. 就会导致出现依赖一直报错.

  5. iOS 开发笔记-获取某个APP素材

    2019.02.01 更新 以下这种方式只适合越狱的手机,目前12.1以后,iTools已经不适合了,请看最下面第二种方式. 有时候,我们看到别人的APP做得挺漂亮的,那么我们想查看该APP的图片素材 ...

  6. Python接口测试实战1(上)- 接口测试理论

    如有任何学习问题,可以添加作者微信:lockingfree 课程目录 Python接口测试实战1(上)- 接口测试理论 Python接口测试实战1(下)- 接口测试工具的使用 Python接口测试实战 ...

  7. sql server 2000系统表sysproperties在SQL 2008中无效的问题

    Sqlserver有一个扩展属性系统表sysproperties,因为只接触过MSSQL2005及以后的版本,在生产库2008版本及联机文档上搜了下都找不到这个系统表,后来发现这个系统表在2005版本 ...

  8. Django Ajax提交数据请求

    <!DOCTYPE html><html lang="en"><head> <meta charset="UTF-8" ...

  9. HDU3336(KMP &plus; dp)

    Count the string Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) ...

  10. 迭代器适配器(二)general inserter的实现

    上节我们实现了back_inserter和front_inserter,接下来是更为普通的插入迭代器,它允许用户指定插入位置. 实现代码如下: #ifndef ITERATOR_HPP #define ...