机房同学借“理解题意”之名在模拟赛时打了很久的 2048。在此表示严厉谴责。

考虑怎么存储状态。进行模拟，每次入栈的元素可能为 \(2\) 或 \(4\)。

  • 如果入栈的元素为 \(2\) 的话，可以证明（模拟）能够一直合并。
  • 但如果入栈元素为 \(4\) 的话且栈顶为 \(2\)，\(2\) 和其以前的元素就再也无法继续合并了。但如果栈顶不为 \(2\) 仍可以合并。

因此我们只需要储存 最后一个可合并的单调递减序列。来看两个实例如下：

128 32 8 4 2
  • 此时如果入栈为 \(2\)，最终合并结果为 \(\{ 128, 32, 16 \}\)。
  • 此时如果入栈为 \(4\)，最终合并结果为 \(\{ 128, 32, 8, 4, 2, 4 \}\)，前面的部分已经不可合并，故只需存储 \(\{ 4 \}\)。
128 32 16 8 4
  • 此时如果入栈为 \(2\)，结果为 \(\{ 128, 32, 16, 8, 4, 2 \}\)，依旧可以合并。
  • 此时如果入栈为 \(4\)，最终合并结果为 \(\{ 128, 64 \}\)。

由于是单减序列，又注意到 \(k \leq 11\)，可以想到用状压来存储。

定义状态：\( \text{dp}[i][s] \) 表示前 \(i\) 个元素，栈内状态为 \(s\) 的方案数。

  • 初始状态：\( \text{dp}[0][0] = 1 \)
  • 状态转移略复杂，大致思路如下：
    • 插入 \(2\)：可以一直合并（单调序列加深）
    • 插入 \(4\)：若栈顶为 \(2\) 则阻断，重新开始一个新段；否则也能继续合并

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
32
33
34
35
36
37
38
39
const int N = 2e3 + 10;
const int P = 1e9 + 7;
int n, m, k;
int val[N];
int dp[N][(1 << 11) + 1];

int32_t main() {
	n = read(), k = read();
	for(int i = 0; i < n; i++) val[i] = read();
	dp[0][0] = 1;
	
	for(int i = 0; i < n; i++) {
		for(int j = 0; j <= (1 << k); j++) {
			int ni = i + 1, nj;
			if(val[i] != 4) {
				// 插入 2
				nj = min((int)(1 << k), j + 2);
				dp[ni][nj] = (dp[i][j] + dp[ni][nj]) % P;
			}
			if(val[i] != 2) {
				// 插入 4
				if(j == (1 << k)) nj = j;
				else if(j & 2) nj = 4;
				else nj = min(j + 4, (int)(1 << k));
				dp[ni][nj] = (dp[i][j] + dp[ni][nj]) % P;
			}
		}
	}
	write(dp[n][(1 << k)]);
	return 0;
}

// i love mike qwq
````

---

[通过记录](https://codeforces.com/contest/413/submission/316087620)