yukicoder : No.1771 A DELETEQ、 No.1772 Many DELETEQs

1772は最速ACできた。
https://yukicoder.me/problems/no/1772

問題

整数x,yに対し以下の問いに答えよ。

x個の文字列"AB"と、y個の文字列"BA"がある。
これらx+y個の文字列を任意の順で連結した文字列Sを考える。
その後、S中の連続する2文字が同じ文字の場合、その2文字を取り除くという作業を任意回数任意の順で行えるとする。

この手順で構成できるSは何通りか。

解法

既存のSの末尾に文字列を追加するとき、以下の手順が考えられる。

• "AB"を1つ消費し、末尾に"AB"を加える。
• "BA"を1つ消費し、末尾に"BA"を加える。
• "BA"と"AB"を1つずつ消費したのち"AA"を消すことで、末尾に"BB"を加える。
• "AB"と"BA"を1つずつ消費したのち"BB"を消すことで、末尾に"AA"を加える。

それ以外に、"BA"と"AB"を合わせた後でいずれも消すこともできるが、これはどの位置で行っても最終的なSに残らないので、最後に行うものとする。

f(x,y) := x個の"AB"とy個の"BA"から構成できるもののうち、上記4つの手順で構成できるユニークな文字列の数
とすると、f(x,y)=f(x-1,y)+f(x,y-1)+2*f(x-1,y-1)となる。

最後に、"BAAB"をまとめて消すケースを考えると、解はsum(f(x-i,y-i))となる。

int A,B;
const ll mo=998244353;

ll dp[4040][4040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	dp[0][0]=1;
	FOR(x,4010) FOR(y,4010) {
		// erase
		// BB
		// AA
		(dp[x+1][y+1]+=2*dp[x][y])%=mo;
		//keep
		(dp[x+1][y]+=dp[x][y])%=mo;
		(dp[x][y+1]+=dp[x][y])%=mo;
	}
	ll ret=0;
	FOR(x,4010) FOR(y,4010) {
		if(x&&y) (dp[x][y]+=dp[x-1][y-1])%=mo;
	}
	
	int Q;
	cin>>Q;
	FOR(i,Q) {
		cin>>x>>y;
		cout<<dp[x][y]<<endl;
	}
}

まとめ

すんなり解けてよかった。