P11216题解 未完成

一场比赛两道模拟是我从未设想过的

---

前言

上一道题想抢题解没抢到 （QAQ我是为了抢题解才去写的上一道啊） ，这题是边做边写的，希望能在今天晚上抢到题解的位置www。

首先每个题都要先找规律，这样子可以简化题目思路，或者发现某些结论题（我说的）。

要找到规律，我们就要手动先去推，理清规则和思路。

---

思路

• 规则1：读题可知，只有当不能继续生成2和不能继续滑动时，才为无解（会用到）。

• 规则2：读题可知，在这一维上，最开始可以没有数字 或 有一个数字（而且总会是一个大数）。

通过手玩和这个潜在的明显规则，可以知道，无论如何，你总是可以通过合并操作让中间成为一个很大的数，然后两边的数递减（就像2 4 8 2这种情况，呈现出一个正三角包）同时易证，不会出现4 2 8这种倒三角包的情况。

——如图，这就形成了一个正三角包，并满足在中间有一个很大的数

这时候我们将有一个大数字在中间的行为叫作垄断（瞎取的一个名字）。

根据规则1，我们把区间拿数字堆满时才算一种情况，所以我们将问题可以看作为 除了中间一个数，如何将左边和右边堆满

• 一个中间（设它坐标叫 $mid$ 吧）垄断的数会把一个区间分为左边和右边的两个区间，通过结论1，可以发现左边的区间大小必为 $mid-1$ ，右边的区间大小必为 $n-mid$。

如$4~8~16~8~2$，其中16是mid数，将整个区间分成 $4~8$ 和 $8~2$ 两段

• （换个行继续说）左边和右边的最大数肯定是在原来的mid旁边，且比mid小的。

当我们在2048中合并出一个数（或一组数）时，如16，我们会用到 $log_2~n$ 格的辅助空间，辅助空间的大小取决于最大值（如要合并出16 8这一组数时，辅助空间的大小取决于16，那么需要4格的辅助空间）

• 左边和右边的区间排列方法应该是类似的，我们可以使用 $dp[i][j]$ 表示给定最大值（2**i表示）和 区间范围大小（j表示）的左右垄断的方案的可能数（要取模）

还是举个例子，当i=4，j=2时有

16 8
16 4
16 2//从dp[i-1][j-1]中得到
8 4
8 2
4 2//从dp[i-1][j]中得到

这6种情况

所以这时候，思路就大概清晰了

先打好dp表（也可以记忆化搜索，根据每组数据的输入去补充dp表），对于每组数据，双重循环枚举中间数的大小（i属于2的乘方倍，i在[2**2至2**x-1]之间）和位置（j下标从1开始，j在1至n之间），让左右两边的可能数dp[i-k?][j-1] * dp[i-k?][n-j]相乘并放进ans，最后输出

如果k盲目的写1贪心的话，你会连样例都过不了，因为你会出现 $4~8~4$ 的神秘结构，实际上是构成不了的。所以现在k是多少还不确定，那就是细节上的问题了，答案就在下文。这里还要引入一个概念。

这是一个隐藏的限制，我将它取名为辅助空间限制

——如图，当需要合并出16时，用到了4格的辅助空间

再看样例，似乎就说得通了

所以说$4~8~4$的情况不存在，k也不能贪心只比垄断数小一位

这时候回到左边-中间-右边的结构。你会发现先堆左边，再堆右边时，左边的辅助空间为 $n-1$，右边的辅助空间为 $n-mid$，先堆右边，再堆左边时，则情况相反，那么我们不妨就只考虑先堆左边的情况，在最后把ans*2

虽然最后发现是一道错题，但是感觉还是挺有思维含量的(苦笑