最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

最新快讯!Codeforces 1097 G Vladislav and a Great Legend 题解 (DP)

来源：博客园


(资料图片)

题目链接

思路

首先看到这种求\(x^k\)形式的，直接无脑转下降幂：\(x^k=\sum_{i=1}^k S2(k,i)\cdot x^{\underline{i}}\)，其中\(S2\)表示第二类斯特林数，\(x^{\underline i}\)表示\(x\cdot(x-1)\cdots(x-i+1)\)。这是一个恒等式。

这题由于\(k\le 200\)，所以可以直接\(O(k^2)\)暴力求出斯特林数。假设现在已经确定了点集\(s\)，要求\(f_s\)。由于\(x^{\underline i}=\binom xi \cdot i!\)，所以只要对所有\(1\le i\le k\)，求出在点集\(s\)构成的虚树中选\(i\)条边的方案数就可以了。考虑对所有的点集\(s\)一起计算答案，我们希望能求出一个数组\(g_i\)表示在树上选择一个大小为\(i\)的边集，并再选一个点集使得这个点集构成的虚树包含边集中的所有边的方案数。算出\(g\)之后就能直接用斯特林数求答案了。

假设现在已经选好了边集，什么样的点集构成的虚树才能包含里面所有的边？每条边都是有两个端点的，一个深度大一个深度小，把深度小的称为上节点，另一个称为下节点。首先找出边集内所有满足"下节点的子树内没有任何被选择的边"的这些边，它们的下节点的子树内(包括下节点本身)必须有至少一个点被选(条件1)。然后再看存不存在一条被选的边满足所有其他被选边都在它的下节点的子树内，如果存在，它的下节点子树外必须有至少一个点被选(条件2)。发现这两个条件合起来就是充要的。到这里应该都不难想。

然后就可以\(dp\)了，\(dp_{i,j}\)表示在点\(i\)的子树中，所有点的父边(包括i)一共有\(j\)条边被选，且选的点集满足条件1的方案数。转移的时候是对所有的儿子做一个背包。\(dp\)的总复杂度看似是\(O(nk^2)\)的，其实是\(O(nk)\)的，这题的重点就是知道这个方法复杂度是对的并且敢写。复杂度证明后面会说。统计答案的话，按照条件2中的那种边存不存在分两种情况讨论，dp的时候对每个节点顺便统计一下即可。

重点：复杂度证明

官方题解写得很不负责，直接就说跟那种两个节点只在LCA处贡献复杂度的证明方式类似，其实根本不一样。

我们要证明的就是总计算量是\(O(nk)\)级别的。首先把树的形态改造一下，容易发现改造之后每个点都只有最多两个儿子，且树中最多有\(2n\)个节点，且对这个树dp的计算量不比之前少，所以对改造之后的树证明复杂度即可。

首先对于任意一个节点做背包的计算量是\(min(k,size(ls))\cdot min(k,size(rs))\)。把节点分成两类，证明这两类节点的总计算量都是\(O(nk)\):

  • 有任意一个儿子的子树大小达到k的。令\(p=min(k,size(ls),size(rs))\)，则这个点的计算量为\(kp\)。我们做dp是在树中从下往上计算的，处理完这个节点后，上面再用到这个节点的子树大小贡献复杂度时，也只会贡献\(min(k,k+p)=k\)，相当于有\(p\)的大小"消失"了，被消耗掉了。并且发现每一个点贡献的大小只能被消耗一次。所以这部分的总计算量是\(O(nk)\)。
  • 其余节点。发现有任意一个儿子的子树大小达到k的节点其实构成了树上包含根的一个连通块，而其余节点是挂在连通块下面的一些子树。把每个这种子树分别拿出来计算复杂度，对于任意一个子树，其中的两个点只会在LCA处贡献复杂度，所以子树内部计算量最多\(size^2\)。而所有子树的\((\sum size)\le n\)，且所有这种子树的\(size\)都是\(O(k)\)级别的(因为子树根的两个儿子大小都达不到k)。所以总计算量仍然是\(O(nk)\)。证毕。

这题的总复杂度也就是\(O(nk)\)。

点击查看代码
#include #define rep(i,n) for(int i=0;i#define fi first#define se second#define mpr make_pair#define pb push_backvoid fileio(){  #ifdef LGS  freopen("in.txt","r",stdin);  freopen("out.txt","w",stdout);  #endif}void termin(){  #ifdef LGS  std::cout<<"\n\nEXECUTION TERMINATED";  #endif  exit(0);}using namespace std;const LL MOD=1e9+7;LL qpow(LL x,LL a){LL res=x,ret=1;while(a>0){if(a&1) (ret*=res)%=MOD;a>>=1;(res*=res)%=MOD;}return ret;}int dp[100010][210],dp2[100010][210][3];LL n,t,sz[100010],pw2[100010],f[100010],s2[210][210];vector  g[100010];void dfs(LL pos,LL par){  sz[pos]=1;  vector  son;  rep(i,g[pos].size()) if(g[pos][i]!=par)  {    dfs(g[pos][i],pos);    sz[pos]+=sz[g[pos][i]];    son.pb(g[pos][i]);  }  rep(i,son.size()+3) rep(j,t+3) rep(k,3) dp2[i][j][k]=0;  dp2[0][0][0]=1;  LL cursum=0;  rep(i,son.size())  {    rep(j,min(cursum+1,t+1)) rep(k,3) if(dp2[i][j][k])    {      (dp2[i+1][j][k]+=(LL)dp2[i][j][k]*pw2[sz[son[i]]]%MOD)%=MOD;      repn(p,min(sz[son[i]],t))      {        if(j+p>t) break;        (dp2[i+1][j+p][min(2,k+1)]+=(LL)dp2[i][j][k]*dp[son[i]][p]%MOD)%=MOD;      }    }    cursum+=sz[son[i]];  }  repn(i,t) dp[pos][i]=(dp2[son.size()][i][1]+dp2[son.size()][i][2])%MOD;  repn(i,t) (dp[pos][i]*=2LL)%=MOD;  repn(i,t-1)  {    LL val=(LL)dp[pos][i]*(pw2[n-sz[pos]]-1+MOD);    (f[i+1]+=val)%=MOD;  }  for(int i=2;i<=t;++i) (f[i]+=(LL)dp2[son.size()][i][2]*pw2[n-sz[pos]]%MOD*2)%=MOD;  for(int i=t-1;i>0;--i) (dp[pos][i+1]+=dp[pos][i])%=MOD;  (dp[pos][1]+=(pw2[sz[pos]]-1+MOD)%MOD)%=MOD;  (f[1]+=(pw2[sz[pos]]-1+MOD)*(pw2[n-sz[pos]]-1+MOD))%=MOD;}int main(){  fileio();  pw2[0]=1;repn(i,100005) pw2[i]=pw2[i-1]*2%MOD;  cin>>n>>t;  LL x,y;  rep(i,n-1)  {    scanf("%lld%lld",&x,&y);    g[x].pb(y);g[y].pb(x);  }  dfs(1,0);  s2[1][1]=1;  for(int i=2;i<=t;++i)  {    s2[i][1]=s2[i][i]=1;    for(int j=2;j

114行的臭代码（恼

关键词： 知道这个