「Codeforces 914H」Ember and Storm's Tree Game

Ember 和 Storm 正在玩游戏。首先,Ember 构造一棵 nn 个节点且每个节点度数不超过 dd 的带节点编号的树 TT 。然后,Storm 选择两个不同的节点 uuvv ,并写下从 uuvv 路径上的节点编号,记为序列 a1,a2aka_1,a_2\cdots a_k 。最后,Ember 在序列中选择一个位置 i(1i<k)i(1\leq i < k) ,并在以下两个操作选择一个执行:

  • 翻转 ai+1aka_{i+1}\cdots a_k 并将这一段加上 aia_i,操作后序列变为 a1a_1ai\cdots a_iak+aia_k+a_iak1+aia_{k-1}+a_iai+1+ai\cdots a_{i+1}+a_i
  • 取负 ai+1aka_{i+1}\cdots a_k 并将这一段加上 aia_i,操作后序列变为 a1a_1ai\cdots a_iai+1+ai-a_{i+1}+a_iai+2+ai-a_{i+2}+a_iak+ai\cdots -a_k+a_i

如果最后的序列是严格单调的,则 Ember 获胜,否则 Storm 获胜。

游戏情形可以用一个元组 (T,u,v,i,op)(T,u,v,i,op) 来描述,opop 为翻转或是取负取决于 Ember 的决策。若 Ember 和 Storm 都使用最优策略(若有多种必胜策略,任选一种执行;若必败,也任选一种执行),试统计所有可能的游戏情形的数量,并输出其取模 mm 的结果。

Constraints

2n2002\leq n \leq 2001d<n1 \leq d < n1m21091 \leq m \leq 2\cdot 10^9

Solution

首先,Ember 一定会构造出一棵能让自己必胜的树。而 Ember 获胜当而仅当原序列 aa 为单调的或是单峰的;且对于每一个合法的序列,有 22 种合法的 (i,op)(i,op) 的组合。没有什么好证明的……在草稿纸上自己模拟一下两种操作就可以得到了。

问题转换为:统计满足以下条件的树的数量 SS :1. 包含nn个节点,2. 每个节点度数不超过 dd ,3. 树上任意两个节点间路径的编号序列为单调的或单峰的。最终答案为 2n(n1)S2\cdot n\cdot(n-1)\cdot S

而对于一棵合法的树,一定存在一个特殊点,满足以这个节点为起点或终点的所有路径都是单调的。为了方便统计,我们令合法树的根节点为特殊点。观察可得,对于一棵合法树,除根节点以外的子树都满足:父亲节点编号大于儿子编号,或是父亲编号小于儿子编号。所以我们只需要统计这两种情况的答案,然后在根节点处拼起来即可。而实际上,这两种情况是等价的。

f(i,j)f(i,j) 表示节点数为 ii ,根节点度数为 jj ,且父亲编号小于儿子编号的方案数。

枚举当前要拼接的子树大小 kk ,钦定根节点编号最小,拼接过来的子树的根节点编号次小,可得到以下递推公式:

f(i,j)=k=1i1f(ik,j1)(i2k1)l=1d1f(k,l)f(i,j)=\sum _{k=1}^{i-1}f(i-k,j-1)\cdot \binom{i-2}{k-1}\cdot \sum _{l=1}^{d-1}f(k,l)

sum(i)=j=1d1f(i,j)sum(i)=\sum _{j=1}^{d-1}f(i,j),可得:

f(i,j)=k=1i1f(ik,j1)(i2k1)sum(k)f(i,j)=\sum _{k=1}^{i-1}f(i-k,j-1)\cdot \binom{i-2}{k-1}\cdot sum(k)

时间复杂度为 O(n3)O(n^{3}) ,初始化 f(1,0)=sum(1)=1f(1,0)=sum(1)=1

(这种方法是在评论区看到的……然后参考了一下wxh大爷的博客官方题解给了另一种统计 ff 数组的方式,要稍微复杂一些,以及因为不保证 mm 是质数,会有一些细节需要处理。详见官方题解,细节处理详见评论区。)

统计出 ff 数组后就可以开始拼接了,枚举满足父亲节点编号小于儿子编号的点数 ii 、度数 jj , 满足父亲节点编号大于儿子编号的度数 kk ,可得到以下公式:

S=i=0n1j=0dk=0djf(i+1,j)f(ni,k)S=\sum _{i=0}^{n-1}\sum _{j=0}^{d}\sum _{k=0}^{d-j}f(i+1,j)\cdot f(n-i,k)

而实际上一棵合法树是可以有多个合法根的,比如最简单的 n=2n=2 的情况,合法根既可以是 11 也可以是 22 。我们可以得出另一个结论,如果一棵树有多个合法根,那么这些点一定构成一条单调链,一端是 j=1j=1k1k≠1 ,另一端是 j1j≠1k=1k=1 ,中间是 j=1j=1k=1k=1 ,我们把这棵树放在第一种情况统计。

得到最终公式:

S=i=0n1j+kd,k1f(i+1,j)f(ni,k)S=\sum _{i=0}^{n-1}\sum _{j+k\leq d,k\neq 1}f(i+1,j)\cdot f(n-i,k)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<cstdio>
#include<algorithm>
#include<cstring>
#define LL long long
using namespace std;
const int N=205;
int n,d,mod;
LL ans,sum[N],c[N][N],f[N][N];
int main()
{
scanf("%d%d%d",&n,&d,&mod);
for(int i=0;i<=n;i++)c[i][0]=1;
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
sum[1]=1;f[1][0]=1;
for(int i=2;i<=n;i++)
{
for(int j=1;j<=d;j++)
for(int k=1;k<i;k++)
f[i][j]=(f[i][j]+f[i-k][j-1]*sum[k]%mod*c[i-2][k-1]%mod)%mod;
for(int j=1;j<=d-1;j++)
sum[i]=(sum[i]+f[i][j])%mod;
}
for(int i=0;i<=n-1;i++)
for(int j=0;j<=d;j++)
for(int k=0;j+k<=d;k++)
if(k!=1)ans=(ans+f[i+1][j]*f[n-i][k]%mod)%mod;
printf("%lld",2*n*(n-1)*ans%mod);
return 0;
}