首页 > 代码库 > hihoCoder #1454 : Rikka with Tree II

hihoCoder #1454 : Rikka with Tree II

2024-09-19 05:21:25   218人阅读

Description

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

Solution

区间DP.

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

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

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

Code

#include <bits/stdc++.h>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<r;i++) res=(res+B(l,i,1)*A(i+1,r,x)%p)%p;	return res;}int main() {	memset(f,0xff,sizeof(f));	scanf("%d",&n);	scanf("%s%s",a+1,b+1);	printf("%lld\n",A(1,n,0));	/*	for(int i=1;i<=n;i++) {		for(int j=i;j<=n;j++) {			cout<<i<<" "<<j<<"->";			cout<<A(i,j,0)<<" "<<A(i,j,1)<<" ";			cout<<B(i,j,0)<<" "<<B(i,j,1)<<endl;		}	}*/	return 0;}

　　

hihoCoder #1454 : Rikka with Tree II


联系
我们