hihoCoder #1454 : Rikka with Tree II

Description

一个\(n\)个节点的树，先根遍历为\(1...n\)。已知两个数组，一个数组表示是否是叶节点，另一个数组表示十分有右兄弟节点...'?'表示未知，求方案数\(n\leqslant 500\).

Solution

区间DP.

DFS序的一段表示一个子树.

\(f[l][r][0/1]\)表示[l,r]变成几个子树，并不是一个...右边是否还能放的方案数...

为了方便我多写了一个函数A,他表示仅有一个子树的方案数..

Code

#include 
using namespace std;

typedef long long ll;
const int N = 505;
const ll p = 998244353;

int n;
char a[N],b[N];
ll f[N][N][2];

ll A(int, int, int);
ll B(int, int, int);

ll A(int l,int r,int x) {
	if(l==r) return (a[l]=='0'||a[l]=='?')&&(b[l]=='?'||b[l]==x+'0');
	if(b[l]!='?'&&b[l]!=x+'0') return 0;
	if(a[l]=='0') return 0;
	return B(l+1,r,0);
}
ll B(int l,int r,int x) {//subtrees
	if(l>r) return 1;
	if(~f[l][r][x]) return f[l][r][x];
	if(l==r) return (a[l]=='0'||a[l]=='?')&&(b[l]=='?'||b[l]==x+'0');
	ll &res=f[l][r][x];res=A(l,r,x);
	for(int i=l;i";
			cout<