题解 石头剪刀布

plaese kill me. && don't forget me.

题目描述

给定 \(n\) 个字符串 \(s_i\) 只包含 0,1,2，现在要捏一个序列 \(A\)，\(s_i\) 表示 \(a_i\) 可以捏成什么。1,2,3 形成环形吊打关系，\(\omega(X)\) 表示序列 \(X\) 最长的吊打子序列，吊打序列指的是对于 \(a_{p_1},\dots,a_{p_k}\) ，除了首位每一位都被前一个吊打。求对于 \(t=1,\dots,n\) 满足 \(\omega(A)=t\) 的 \(X\) 有多少个。

\(n\leq 2000\)

题解

先考虑给定一个序列 \(\omega(A)\) 怎么求，简单 dp，设 \(f[i][0/1/2]\) 表示前 \(i\) 位以 \(0/1/2\) 结尾的最长长度，假设 \(x\) 吊打 \(y\)，\(f[i][y]=\max\{f[j][x]+1\}\)。

发现关心 \(f[i][0/1/2]\)，那么弄更好做的状态 \(g[i][x][y][z]\) 表示前 \(i\) 位以 \(0/1/2\) 结尾的吊打子序列最长为 \(x/y/z\) 的方案数，转移就跟自己和吊打 add1 取 max 就可以啦 qwq

然后到了喜闻乐见的优化环节，题目特性对于 \(x,y,z\) 有类似 \(|x-y|\leq 2\) 的关系，于是乎有用的状态就很少啦，把后两维换成 \(-2\to2\)，第一位加个滚动就可以愉快的 AC 了捏。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=2023, P=998244353;
int n, lsy[N][4], ans[N];
int f[2][N][5][5];

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; ++i) {
		string s; cin >> s;
		for(int j=0; j<s.size(); ++j)
			lsy[i][s[j]-'0']=1;
	}
	f[0][0][2][2]=1;
	for(int i=1; i<=n; ++i) {
		int u=i%2, v=1-u;
		memset(f[u],0,sizeof(f[u]));
		for(int j=0; j<i; ++j)
			for(int a=0; a<5; ++a)
				for(int b=0; b<5; ++b) {
					if(!f[v][j][a][b]) continue;
					int x=j, y=j+a-2, z=j+b-2, qwq;
					if(lsy[i][0]) {
						qwq=max(x,z+1);
						f[u][qwq][y-qwq+2][z-qwq+2]+=f[v][j][a][b];
						f[u][qwq][y-qwq+2][z-qwq+2]%=P;
					}
					if(lsy[i][1]) {
						qwq=max(x+1,y);
						f[u][x][qwq-x+2][z-x+2]+=f[v][j][a][b];
						f[u][x][qwq-x+2][z-x+2]%=P;
					}
					if(lsy[i][2]) {
						qwq=max(y+1,z);
						f[u][x][y-x+2][qwq-x+2]+=f[v][j][a][b];
						f[u][x][y-x+2][qwq-x+2]%=P;
					}
				} 
	}
	for(int i=0; i<=n; ++i)
		for(int a=0; a<5; ++a)
			for(int b=0; b<5; ++b) {
				ans[max(max(i,i+a-2),i+b-2)]+=f[n%2][i][a][b];
				ans[max(max(i,i+a-2),i+b-2)]%=P;
			}
	for(int i=1; i<=n; ++i)
		cout << ans[i] << ' ';
	return 0;
}