CF1767C

我们先讨论，对序列 \(A=a_{ij}a_{i+1j}...a_{j-1j}a_{jj}\) 来说什么是合法情况:
不难发现当 \(i==j\) 时，\(a_{ij}=0\) 与 \(a_{ij}=1\) 情况相同，而\(a_{ij}=2\) 的情况不存在，此时\(a_{ij}=2\) 就是不合法的情况。
再来想象下这样一种情况:
\(a_{kj}=0 (k<j)\)
这里有两个问题:

1. k为什么要小于j
2. \(a_{k-1j}\) 的值可以取多少
   现给出解答:
3. 当\(k=j\) 时，会有\(a_{kj}=0\) 和 \(a_{kj}=1\)情况相同这么一个性质，此时为一个特例，我们要找出普遍的规律，所以从\(k<j\) 开始考虑
4. \(a_{k-1j}\) 有三种可能的取值，现一一讨论其合理性:
   1. \(a_{k-1j}=0\) ,由于\(a_{kj}\) 也为0，不会产生冲突，所以合法
   2. \(a_{k-1j}=1\) ，对于\(a_{kj}=0\)我们可以将其展开讨论，此时又分为三种情况:
      1. \(s_{k-j}\) : 全为0
      2. \(s_{k-j}\) : 全为1
      3. \(s_{k-j}\) : 至少有一个1，并且至少有一个0
         而\(a_{k-1j}=1\)只能满足前两种情况，第三种会产生冲突，所以不合法
   3. \(a_{k-1j}=2\) ，根据上述\(a_{kj}=0\)的情况，对情况1来说，只要使\(s_{k-1}=1\),即可满足条件，同理2，只需\(s_{k-1}=0\)即可满足，情况三显然满足，所以合法
      当\(a_{kj}=1\) 或 \(a_{kj}=2\) 时，\(a_{k-1j}\)的值的推导过程与上述类似，这里不多加赘述，直接给出结论:
      当\(a_{kj}=1\)时，\(a_{k-1j}=1\)或\(a_{k-1j}=2\)
      当\(a_{kj}=2\)时，\(a_{k-1j}=2\)
      有上述信息我们可以粗略的将序列\(A\)分为两大类:
5. \(2...21...1\)
6. \(2...20...0\)
   我们又可以发现对于序列\(0...0\)又可以划分为：\(1...1\), \(21...1\), \(221...1\), \(2...21\), \(2...2\) 这样我们就可以将两大类转化为一大类，就可以以\(2,1\) 分界线来dp：
   
   答案就是把所有满足限制的 \(f_{nj}\) 相加，转移过程中还要对不合法的转移进行限制。
   判断不合法条件：对于判断 \(f_{ij}\) 是否合法，只需要看所有\(a_{ki}\) 的限制，其中 \(k\in[1,i]\) ，\(j\) 是分界线。如果限制为 2 ，则必须保证 \(j\)>\(k\) ；如果限制为 1 ，则必须保证 \(j<=k\) .
   代码如下:

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N=110,mod=998244353;
ll n,g[N][N],f[N][N];

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		for(int j=i;j<=n;j++)
			cin>>g[i][j];

	f[1][1]=2;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=i;j++)
		{
			bool flag=false;
			for(int k=1;k<=i;k++)
			{
				if(g[k][i]==1 && k<j) flag=true;
				if(g[k][i]==2 && k>=j) flag=true;
			}

			if(flag) f[i][j]=0;
			f[i+1][j]=(f[i+1][j]+f[i][j])%mod;
			f[i+1][i+1]=(f[i+1][i+1]+f[i][j])%mod;
		}

	ll ans=0;
	for(int i=1;i<=n;i++) ans=(ans+f[n][i])%mod;

	cout<<ans<<endl;

	return 0;
}

部分参考每日一棵splay大佬的这篇文章