ARC059F Unhappy Hacking

, ,

ARC059F Unhappy Hacking

Description

https://www.luogu.com.cn/problem/AT_arc059_d

Solution

贡献用到了再算，或者删除的时候再算贡献 的想法一定要记住！！！

显然有一种天真的 $O(n^3)$ 的 dp。但是过不了。

注意到根本不需要知道 $s$ 这个字符串里面是什么。令 $f_{i,j}$ 表示按了 $i$ 个按键，匹配到 $j$ 个位置。

  • 如果按下了 0/1，则有 $f_{i,j}\gets f_{i-1,j-1}$
  • 如果按下了删除键，则我们不关心被删除的那个位置原来是什么，0/1 都可以，有 $f_{i,j}\gets 2\times f_{i-1,j+1}$
  • $f_{i,0}\gets f_{i-1,0}$。

复杂度 $O(n^2)$。

1
2
3
4
5
6
7
8
9
10
11
12
string s;
int n,m;
signed main(void){
	int i,j;
	read(n);cin>>s;
	for (f[0][0]=1,i=1;i<=n;i++) {
		for (j=0;j<=n;j++)
			f[i][j]=(f[i-1][max(j-1,0ll)]+2*f[i-1][j+1])%mod;
	}
	printf("%lld",f[n][s.size()]);
	return 0;
}