[题解] Atcoder ARC 142 D Deterministic Placing 结论，DP

2022/6/21 23:23:50

编程Tag： 节点 DP pos Son 题解 Placing mod REP Atcoder

本文主要是介绍[题解] Atcoder ARC 142 D Deterministic Placing 结论，DP，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目
(可能有点长，但是请耐心看完，个人认为比官方题解好懂:P)

首先需要注意，对于任意节点i上的一个棋子，如果在一种走法中它走到了节点j，另一种走法中它走到了节点k，那么这两种走法进行完后，棋子占据的节点集合不可能相同，因为在这两种走法中，节点i必有两个子树中的棋子数量不同。所以，题目中的"被占据的集合唯一"等价于"每个棋子走向的节点唯一"。

根据题意，一个初始状态合法当且仅当这个状态可以进行任意次操作，且进行k步操作后，接下来一步操作唯一(不管这样走之后，是否还能进行无限次操作)。先不考虑"唯一"，只考虑怎么使得可以进行无限次操作。我们可以把树分成一些链，每条链初始有一个端点是空的，其他节点都被棋子占据。第一步操作时，把每条链上的每个棋子，都往这条链上的空节点方向移动一步。后面的每一步操作都可以在这两个状态之间反复横跳，满足了"无限次"的要求。现在把"唯一"的条件加进来，发现树上的每个节点都必须恰好被一条链覆盖到，不然肯定存在一个没被覆盖的节点i，使得在某一步中可以把一个本应该走到其他位置的棋子移到这个点上，使得方案不唯一。

如果一个状态合法，唯一的操作方案就是：每条链上的棋子在这条链上左右横跳。现在来看看哪些"链划分"是不合法的(操作方案不唯一)。我们把每条链没有棋子的端点称为"0端"，有棋子的端点称为"1端"，这两个统称端点；其它点称为中间点。

先给出结论：两个相邻节点x、y，如果出现以下情况之一，这种状态就不合法，否则合法：1.一个是中间点，一个是端点，且属于不同的链；2.两个点都是1端(属于不同的链)；3.两个点都是0端(显然也属于不同的链)。

证明：

1.出现以上情况的一定不合法

如果x是中间点且y是端点，不属于同链，如果y是1则x可以在第一步向y移动，y是0则x可以在第二步向y移动，均不唯一
都是1端，则可以合并成一条链，并扔掉其中一条链的0端，不唯一
都是0端，则移动一次后可以合并成一条链

2.不出现的一定合法

只需要证明任意一种没有上述情况的状态，第一步操作都唯一。因为操作一次后达到的状态是与其对称的，再操作一次又回到了这个状态。

考虑一个中间节点会不会不守本分，跑到其他的链去。那肯定是跑到了另一条链的一个中间节点，原本要到这个点的棋子就必须找另一条路，它可以走到另一条链，也可以向着本链的1端走一步，第一种走法循环了，所以若干次后总会走上第二种。走上第二种后，类似的，总能规约到一个1端棋子必须走到别的链(的0端)。原来要走到这个0端节点的棋子是在一个中间位置上的，它又需要走到别的链，或者向本链1端走\(\cdots\)

发现陷入了死循环，所以总有一个点找不到出路，所以方案不唯一的情况此时不会出现。

接下来对合法的链划分计数。考虑树形dp，dp过程中不考虑每条链的方向(即忽略0端和1端的位置)

\[\begin{align} dp[*][0]&:当前是中间节点，所在链的两端点都在子树内\\ dp[*][1]&:中间节点，链只有一个端点在子树内\\ dp[*][2]&:端点，与之匹配的端点不在子树内\\ dp[*][3]&:端点，匹配的端点在子树内 \end{align} \]

转移比较简单，不一一赘述。考虑怎么加入每条链方向的影响，如果两条链端点相邻，则在这两条链间连边。最后每一个连通块都有2种方案。对于任意一个中间节点，它在树上的儿子中除了2个，其他都跟它属于不同的连通块，当前dp到的节点为中间节点时乘上对应方案数即可。

时间复杂度\(O(n)\)。

点击查看代码

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<n;++i)
#define repn(i,n) for(int i=1;i<=n;++i)
#define LL long long
#define pii pair <int,int>
#define pb push_back
#define fi first
#define se second
#define mpr make_pair

using namespace std;

const LL MOD=998244353;

LL qpow(LL x,LL a)
{
	LL res=x,ret=1;
	while(a>0)
	{
		if((a&1)==1) ret=ret*res%MOD;
		a>>=1;
		res=res*res%MOD;
	}
	return ret;
}

LL n,dp[200010][4],dp2[200010][3],suf[200010];
vector <LL> g[200010];

void dfs(LL pos,LL par)
{
  vector <LL> son;
  rep(i,g[pos].size()) if(g[pos][i]!=par)
  {
    dfs(g[pos][i],pos);
    son.pb(g[pos][i]);
  }
  //2
  dp[pos][2]=1;rep(i,son.size()) (dp[pos][2]*=dp[son[i]][3])%=MOD;
  //3
  suf[0]=1;rep(i,son.size()) suf[i+1]=suf[i]*dp[son[son.size()-i-1]][3]%MOD;
  LL bas=1;
  rep(i,son.size())
  {
    (dp[pos][3]+=(dp[son[i]][1]+dp[son[i]][2])%MOD*bas%MOD*suf[son.size()-i-1])%=MOD;
    (bas*=dp[son[i]][3])%=MOD;
  }
  //1
  suf[0]=1;rep(i,son.size()) suf[i+1]=suf[i]*dp[son[son.size()-i-1]][0]%MOD;
  bas=1;
  rep(i,son.size())
  {
    (dp[pos][1]+=(dp[son[i]][1]+dp[son[i]][2])%MOD*bas%MOD*suf[son.size()-i-1])%=MOD;
    (bas*=dp[son[i]][0])%=MOD;
  }
  //0
  rep(i,son.size()+3) rep(j,3) dp2[i][j]=0;
  dp2[0][0]=1;
  rep(i,son.size()) rep(j,3)
  {
    if(j<2) (dp2[i+1][j+1]+=dp2[i][j]*(dp[son[i]][1]+dp[son[i]][2]))%=MOD;
    (dp2[i+1][j]+=dp2[i][j]*dp[son[i]][0])%=MOD;
  }
  dp[pos][0]=dp2[son.size()][2];
  LL mul=(LL)son.size()-2;
  if(mul>0) (dp[pos][0]*=qpow(2,mul))%=MOD;
  ++mul;
  if(mul>0) (dp[pos][1]*=qpow(2,mul))%=MOD;
}

int main()
{
  cin>>n;
  LL x,y;
  rep(i,n-1)
  {
    scanf("%lld%lld",&x,&y);
    g[x].pb(y);g[y].pb(x);
  }
  dfs(1,0);
  cout<<(dp[1][0]+dp[1][3])*2LL%MOD<<endl;
	return 0;
}

这篇关于[题解] Atcoder ARC 142 D Deterministic Placing 结论，DP的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

[题解] Atcoder ARC 142 D Deterministic Placing 结论，DP

相关编程文章