[ARC059F] Unhappy Hacking 题解

题目链接：[ARC059F] Unhappy Hacking

题意：

Sig已经自己组装了一台键盘。为了达到极致的简单性，这个键盘上只有三个按键：0 键、1 键和退格键。 一开始，他在使用这个键盘的纯文本编辑器。该编辑器始终显示一个字符串（可能为空）。在编辑器启动后，此字符串为空。当按下键盘上的每个键时，字符串发生以下更改：

• 0 键：在字符串的右侧插入一个数字 0。
• 1 键：在字符串的右侧插入一个数字 1。
• 退格键：如果字符串为空，则不发生任何变化。否则，删除字符串的最右边的字母。

Sig启动了编辑器，并总共按下了这些键$N$次。结果，编辑器显示一个字符串$s$。找出按下这些键的方式的数量，对$10^9+7$取模。

$1 \le N \le 5\times 10^3,1\le |s| \le N$ ，且 $s$ 仅由 0 和 1 构成。

“人不能两次踏进同一条河流。”

每次按下按键的那个人都不是上一次按下按键的那个人（大雾）

设 $f_{i,j}$ 表示按第 $i$ 次按键后匹配了 $j$ 个字符的方案数，

定义 $f_{0,0}=1$ ，并且 $j<0$ 时为 $f_{i,j}=f_{i,0}$ ，则

$$f_{i,j} = f_{i-1,j-1}+2f_{i-1,j+1}$$

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
const int mod = 1e9 + 7;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e3 + 15))

int n,dp[N][N]; string s;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> s; dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j <= i; j++)
            dp[i][j] = (dp[i - 1][max(j - 1, 0ll)] + dp[i - 1][j + 1] * 2 % mod) % mod;
    cout << dp[n][s.size()] << '\n';
    return 0;
}

---

参考文献：

[1] 【题解】AT2022 [ARC059D] Unhappy Hacking - dd_d 的博客 - 洛谷博客

---

题外话：

《纯粹理性批判》还没看完呢，烦。