#C240930B. Deterministic Heap (Easy Version)

标签（Label）

动态规划

网址（Website）

Deterministic Heap (Easy Version) - 洛谷

Problem - E1 - Codeforces

题目（Problem）

这是问题的简单版本。两个版本的区别在于确定性最大堆的定义、时间限制以及对 $n$ 和 $t$ 的约束。只有两个版本的问题都解决了，你才能进行破解。

考虑一棵完美二叉树，大小为 $2^n - 1$，节点编号为 $1$ 至 $2^n-1$，根节点为 $1$。对于每个顶点 $v$ ( $1 \le v \le 2^{n - 1} - 1$ )，顶点 $2v$ 是它的左子顶点，顶点 $2v + 1$ 是它的右子顶点。每个节点 $v$ 也有一个赋值 $a_v$。

定义操作 $\mathrm{pop}$ 如下：

将变量 $v$ 初始化为 $1$；
重复以下过程，直到顶点 $v$ 成为叶子（即直到 $2^{n - 1} \le v \le 2^n - 1$）：
1. 在 $v$ 的子顶点中，选择值较大的一个，并将该顶点记为 $x$；如果它们的值相等（即 $a_{2v} = a_{2v + 1}$），则可以任选一个；
2. 将 $a_x$ 赋值给 $a_v$（即 $a_v = a_x$）；
3. 将 $x$ 赋值给 $v$（即 $v = x$）；
将 $-1$ 赋值给 $a_v$（即 $a_v = -1$）。

如果 $\mathrm{pop}$ 的操作是唯一的，那么就说 $\mathrm{pop}$ 的操作是确定的。换句话说，只要在它们之间进行选择， $a_{2v} \neq a_{2v + 1}$ 就会成立。

如果每个顶点 $v$（ $1 \le v \le 2^{n - 1} - 1$）的 $a_v \ge a_{2v}$ 和 $a_v \ge a_{2v + 1}$ 都成立，那么这棵二叉树就叫做最大堆。

如果 $\mathrm{pop}$ 操作在第一次操作时是确定的，那么最大堆就是确定的。

起初，每个顶点 $v$（ $1 \le v \le 2^n - 1$）都是 $a_v = 0$，而你的目标是计算通过应用下面的操作 $\mathrm{add}$ 产生的不同确定性最大堆的数量，正好是 $k$ 次：

选择一个整数 $v$ ( $1 \le v \le 2^n - 1$)，并为 $1$ 和 $v$ 之间路径上的每个顶点 $x$ 添加 $1$ 到 $a_x$。

如果两个堆中有一个节点的值不同，则认为这两个堆是不同的。

由于答案可能比较大，请打印答案对 $p$ 取模。

我们可以用如下的数学表达式来表示这个问题：

设 $f(n, k, p)$ 表示在完美二叉树大小为 $2^n - 1$，进行 $k$ 次 $\mathrm{add}$ 操作后，使 $\mathrm{pop}$ 操作有确定性的最大堆的数量对 $p$ 取模的结果。

我们需要计算 $f(n, k, p)$。

题解（Solution）

$\qquad$这道题的题目读起来就很难受，我最开始读的时候一直没理解到 $\mathrm{pop}$ 操作是一个类似 $\mathrm{dfs}$ 的函数。

$\qquad$ 很明显可以想到一个动态规划（$\mathrm{dp}$），$f_{i,j}$ 表示第 $i\sim n$ 层用了 $j$ 次 $\mathrm{add}$ 操作的方案数，最终的答案就是 $f_{1,k}$。设当前层左子树操作了 $p_1$ 次，右子树操作了 $p_2$ 次，满足 $p_1+p_2\le j$，那么当 $p_1>p_2$ 时，$f_{i+1,p_1}$ 对当前的 $f_{i,p_1+p_2+q}$ 有贡献，其中 $q$ 表示在当前父节点操作了多少次。我们可以先计算出上一层对 $f_{i,p_1+p_2}$ 的贡献，然后在使用前缀和计算 $f_{i,p_1+p_2}$ 对 $f_{i,p_1+p_2+q}$ 的贡献就好了。

$\qquad$除了 $f_{i+1,p_1}$ 对 $f_{i,p_1+p_2}$ 有贡献，我们还要算上操作数少的子树能有多少种情况。相当于每次选子树内的一个点，并对其进行 $\mathrm{add}$ 操作，对不同点 $\mathrm{add}$ 贡献不同，但是 $\mathrm{add}$ 的顺序不会影响最后的方案数。这样做十分的麻烦，于是我们考虑增添一个 $g_{i,j}$ 表示在没有 $\mathrm{pop}$ 确定性的要求下的方案数，$i,j$ 的定义与 $f_{i,j}$ 相同，便有：

if(p1>p2) f[i][j] += 2ll * f[i+1][p1] * g[i+1][p2] % mod;//左右子树都有可能
g[i][j] += g[i+1][p1] * g[i+1][p2] % mod;

$\qquad$注意多组数据的清空和取模。

代码（Code）

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
	char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
	while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 505;
bool ST;

int n,k,mod;
inline void add(int &x,int y){if(x+=y>=mod)x-=mod;}

int f[N][N], g[N][N];
inline int solve(){
	For(i,0,k) f[n][i] = g[n][i] = 1;
	Rof(i,n-1,1){//走到了第 i 层 
		For(j,0,k){//大的子树用了 j 次操作 
			For(p,0,k-j){//小的子树使用了 p 次 
				g[i][j+p] += g[i+1][j]*g[i+1][p]%mod;
				if(j>p) f[i][j+p] += 2ll * f[i+1][j] * g[i+1][p]%mod;
			}
		}
		For(j,1,k) (f[i][j] += f[i][j-1])%=mod, (g[i][j] += g[i][j-1])%=mod; 
	}return f[1][k]%mod;
}

bool ED;
signed main(){
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T=rd(), Tim = clock();
	while(T--){
		n=rd(),k=rd(),mod=rd();
		cout<<solve()<<'\n';
		memset(f,0,sizeof f);
		memset(g,0,sizeof g);
	}return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}