【ICPC2022济南站】【树形dp】【删物品背包dp】C.DFS Order 2
admin
2024-04-15 08:56:30
0

【题意】

题目链接:https://codeforces.com/gym/104076/problem/C
简要题意:给定一棵n个点的有根树,对于所有的二元组(i,j)(i,j)(i,j)求这颗树所有可能的dfs序中有多少个dfs序满足第iii个点出现在dfs序第jjj个位置。

【思路】

赛场上假了无数次以后,我终于才理清楚了这题的dp思路。
状态定义:
定义dp[u][i]dp[u][i]dp[u][i]表示只考虑uuu子树外的点的情况下,dfs序中在uuu前面有iii个点的方案数。注意,这个dpdpdp值并不能直接作为答案,还要乘上uuu子树内部的所有可能的dfs序方案数。显然这个dpdpdp的取值与uuu子树的情况无关,因此这道题dpdpdp的转移与一般树形dpdpdp不同,这道题应当自上而下用父亲的信息更新儿子的信息。上文提到过,为了得到答案,我们还需要uuu子树内部的dfs序方案数量,因此定义dp2[u]dp2[u]dp2[u]表示uuu子树内的dfs序方案数。
状态转移
设我们当前在uuu点,我们考虑更新uuu的一个儿子vvv的dpdpdp信息,我们需要知道dfs序有多少个点在vvv前面,我们把这些点分为在uuu的子树内和uuu的子树外两类,最后类似背包的思路合并即可。

  • 对于uuu子树外的点的信息,我们通过uuu的dpdpdp值即可获得;
  • 对于uuu子树内的点,在vvv前面的点的数量取决于uuu的儿子们的排列顺序,我们可以把u的所有儿子的子树大小sizsizsiz拿来做一次背包,与一般背包不同的是,后续用背包的结果更新dp值时还需要考虑放置顺序,因此我们还需要加一维表示当前背包的大小,便于考虑物品顺序。设c[i][j]c[i][j]c[i][j]表示放置了iii个物品,总大小为jjj的方案数,考虑放置子树vvv,则转移显然:c[i][j]=c′[i][j]+c′[i−1][j−siz[v]]c[i][j]=c'[i][j]+c'[i-1][j-siz[v]]c[i][j]=c′[i][j]+c′[i−1][j−siz[v]]
    c′c'c′表示未考虑vvv的dp值,ccc表示已考虑vvv的dp值,因此iii这一维倒序枚举更新即可不需要额外的数组。若我们要求vvv的dp值,则我们背包里需要删除vvv这个物品。由于背包dp的本质是一种多项式的卷积(此处的dp等价于c(y,x)=∏v∈sonu(1+y∗xsiz[v])c(y,x)=\prod_{v\in son_u}(1+y*x^{siz[v]})c(y,x)=∏v∈sonu​​(1+y∗xsiz[v])),放置顺序无关紧要,我们不妨假设vvv是最后一个加入背包的物品。此时相当于我们已知c数组而需要求c′c'c′数组(注意,这里的c′c'c′数组在参考代码里就是ddd数组)。移项可得转移:
    c′[i][j]=c[i][j]−c′[i−1][j−siz[v]]c'[i][j]=c[i][j]-c'[i-1][j-siz[v]]c′[i][j]=c[i][j]−c′[i−1][j−siz[v]]
    在得到c′c'c′数组后,设在vvv前面有jjj个uuu子树内的点的方案数为b[j]b[j]b[j],uuu一共有cntcntcnt个儿子,则有转移:
    b[j]=∑i=0cnt−1c′[i][j]∗i!∗(cnt−1−i)!b[j]=\sum_{i=0}^{cnt-1} c'[i][j]*i!*(cnt-1-i)!b[j]=i=0∑cnt−1​c′[i][j]∗i!∗(cnt−1−i)!
    而对于uuu这个点,它在dfs序中一定位于其他uuu子树内的点的前面,我们可以在设置ccc数组初值时考虑它,即:c[0][1]=1c[0][1]=1c[0][1]=1。
  • 现在,我们已知bbb数组和dpdpdp数组,考虑用背包dp的思路对它们进行合并。但是我们目前仅考虑了u的儿子之间的排列顺序,尚未考虑这些儿子子树内的排序方案。设B=∏x∈sonudp2[x]B=\prod_{x\in son_u}dp2[x]B=∏x∈sonu​​dp2[x]。当我们用这些信息去更新vvv的dp值时,需要注意除去常数B中和vvv子树有关的信息。诚然,不除去这部分信息的话,我们直接得到的就是vvv的答案数组,但是这并不利于我们进一步dfs求v的子树的dp信息,因此我们在这里的处理是除去这部分信息。即定义C=∏x∈sonu,x≠v=Bdp2[v]C=\prod_{x\in son_u,x\neq v}=\frac B {dp2[v]}C=∏x∈sonu​,x​=v​=dp2[v]B​,有以下转移:
    对于i∈[1,n],dp[v][i]=C∗∑j=0siz[u]b[j]∗dp[u][i−j]对于i\in [1,n],dp[v][i]=C*\sum_{j=0}^{siz[u]}b[j]*dp[u][i-j]对于i∈[1,n],dp[v][i]=C∗j=0∑siz[u]​b[j]∗dp[u][i−j]
    (jjj的上确界是小于siz[u]siz[u]siz[u]的,比赛时为了求稳所以定枚举上界为siz[u]siz[u]siz[u])

而对于dp2数组,我们需要在处理dp数组前就提前dfs一次先得到它。设uuu总共有cntcntcnt个儿子,考虑uuu子树内所有可能的dfs序,转移显然:
dp2[u]=cnt!∗∏dp2[v]dp2[u]=cnt!*\prod dp2[v]dp2[u]=cnt!∗∏dp2[v]
此时,第iii个点出现在dfs序中第jjj个位置的方案数就是dp[i][j−1]∗dp2[i]dp[i][j-1]*dp2[i]dp[i][j−1]∗dp2[i]。
参考代码:(比赛时写的代码)

#include
#define ll long long
using namespace std;
const int N=505,mod=998244353;
int n,dp[N][N],siz[N],c[N][N],d[N][N],b[N],fac[N],dp2[N];
vectorg[N];
void Add(int&x,int y){((x+=y)>=mod)&&(x-=mod);
}
inline int mul(int x,int y){return 1ll*x*y%mod;
}
inline int dec(int x,int y){return xint ret=1;while(b){if(b&1)ret=mul(ret,a);a=mul(a,a);b>>=1;}return ret;
}
void dfs1(int u,int fa){siz[u]=1;dp2[u]=1;int cnt=0;for(int v:g[u]){if(v==fa)continue;cnt++;dfs1(v,u);siz[u]+=siz[v];dp2[u]=mul(dp2[u],dp2[v]);}dp2[u]=mul(dp2[u],fac[cnt]);
}
void dfs2(int u,int fa){int cnt=0,sum=1;memset(c,0,sizeof c);c[0][1]=1;int lsr=1;for(int v:g[u]){if(v==fa)continue;cnt++;sum+=siz[v];lsr=mul(lsr,dp2[v]);for(int i=cnt;i>=1;i--)for(int j=sum;j>=siz[v];j--)Add(c[i][j],c[i-1][j-siz[v]]);}for(int v:g[u]){if(v==fa)continue;memset(d,0,sizeof d);for(int i=0;i<=cnt;i++)for(int j=0;j<=siz[u];j++)d[i][j]=dec(c[i][j],(j>=siz[v]&&i>0)?d[i-1][j-siz[v]]:0);memset(b,0,sizeof b);for(int i=0;iif(v!=fa)dfs2(v,u);}
}
int main()
{scanf("%d",&n);fac[0]=1;for(int i=1;i<=n;i++)fac[i]=mul(fac[i-1],i);for(int i=2;i<=n;i++){int u,v;scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dp[1][0]=1;dfs1(1,0);dfs2(1,0);for(int i=1;i<=n;i++){for(int j=0;j

相关内容

热门资讯

安卓系统音乐软件推荐,五大热门... 你有没有发现,手机里音乐软件那么多,挑一款适合自己的真心不容易啊!安卓系统上的音乐软件更是五花八门,...
安卓系统刷三星系统,轻松刷入最... 你有没有想过,你的安卓手机其实可以变身成三星的旗舰机呢?没错,就是那种屏幕大、性能强、系统流畅的旗舰...
塞班系统可以转为安卓,跨越时代... 你知道吗?现在科技的发展真是让人眼花缭乱,连我们曾经熟悉的塞班系统也能华丽转身,变成安卓系统呢!是不...
安卓系统如何录像剪辑,录像剪辑... 亲爱的手机控们,你是否有过这样的经历:在某个瞬间,你捕捉到了一段令人难忘的画面,却因为没来得及记录而...
安卓系统强行提高配置,配置提升... 最近你的安卓手机是不是感觉有点儿“发烧”了?没错,就是那种配置突然“升级”的感觉。你是不是也觉得,手...
安卓系统能做设计吗,探索安卓系... 你有没有想过,安卓系统竟然也能做设计?是的,你没听错,这个我们日常使用的手机操作系统,竟然也能成为设...
安卓系统几年后使用,探索多年使... 你有没有想过,那些陪伴我们多年的安卓手机,它们现在过得怎么样了呢?安卓系统,这个曾经让我们爱恨交加的...
平板安卓苹果双系统,安卓与苹果... 你有没有想过,拥有一台既能运行安卓系统,又能使用苹果系统的平板电脑,那该是多么酷炫的事情啊!想象一边...
嘉和病历系统安卓,便捷医疗信息... 你有没有听说过嘉和病历系统安卓版?这可是医疗行业的一大神器呢!想象医生们拿着手机就能轻松管理病历,患...
安卓10更改系统号,揭秘系统编... 你知道吗?最近安卓系统又来了一次大更新,安卓10正式上线了!这次更新可是带来了不少新功能,其中最引人...
小米墨水屏 安卓系统,融合科技... 你知道吗?在科技日新月异的今天,电子阅读器市场也迎来了新的活力。而小米,这个我们熟悉的品牌,最近推出...
系统软件最少的安卓系统,基于最... 你有没有想过,手机系统就像是我们生活的操作系统,有时候太复杂了,让人感觉头都大了。今天,我要给你介绍...
安卓系统关闭应用推荐,安卓系统... 你有没有发现,手机里的安卓系统最近有点儿“小情绪”,总是给你推荐一些你根本不感兴趣的应用?别急,今天...
车载安卓系统如何用,智能驾驶体... 你有没有想过,你的车载安卓系统其实是个隐藏的宝库呢?没错,就是那个你每天开车时几乎不离手的那个屏幕,...
安卓系统更新如何取消,```p... 你有没有遇到过这种情况:安卓手机的系统更新推送得让人有点头疼,有时候更新后的系统还各种不适应。别急,...
安卓系统源码修改练习,从零开始... 亲爱的技术爱好者,你是否曾梦想过深入安卓系统的内核,亲手修改源码,让手机变得更加个性化?那就让我们一...
安卓考勤系统论文,基于安卓平台... 你有没有想过,每天打卡上班,是不是也能变得有趣起来呢?没错,就是那个我们每天都要面对的安卓考勤系统。...
安卓系统哪家流畅度,安卓系统流... 手机里的安卓系统,就像是每个人的小世界,各有各的风采。但说到流畅度,这可是大家最关心的问题了。今天,...
安卓开不了定位系统,安卓设备定... 最近是不是发现你的安卓手机定位系统突然罢工了?别急,别慌,今天就来给你详细解析一下这个问题,让你轻松...
安卓系统怎么设置airpod,... 你有没有发现,自从AirPods问世以来,它就成为了科技界的宠儿?这款无线耳机不仅音质出众,而且连接...