結果

問題 No.3098 Linear Reversi
ユーザー kotatsugame
提出日時 2025-04-06 17:10:39
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 136 ms / 4,000 ms
コード長 2,262 bytes
コンパイル時間 1,342 ms
コンパイル使用メモリ 87,120 KB
実行使用メモリ 78,684 KB
最終ジャッジ日時 2025-04-06 17:10:44
合計ジャッジ時間 4,190 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<set>
#include<cassert>
#include<atcoder/modint>
using namespace std;
using mint=atcoder::modint998244353;
set<string>naive(int N)
{
	set<string>ret,vis;
	queue<string>Q;
	{
		string fst(N,'?');
		Q.push(fst);
		vis.insert(fst);
	}
	while(!Q.empty())
	{
		string s=Q.front();Q.pop();
		bool fn=false;
		for(int i=0;i<N;i++)if(s[i]=='?')
		{
			fn=true;
			for(char c:{'o','x'})
			{
				auto t=s;
				char vc=c=='o'?'x':'o';
				{
					int l=i-1;
					while(l>=0&&s[l]==vc)l--;
					if(l>=0&&s[l]==c)
						for(int k=l;k<i;k++)t[k]=c;
				}
				{
					int r=i+1;
					while(r<N&&s[r]==vc)r++;
					if(r<N&&s[r]==c)
						for(int k=i;k<r;k++)t[k]=c;
				}
				t[i]=c;
				if(vis.find(t)==vis.end())
				{
					vis.insert(t);
					Q.push(t);
				}
			}
		}
		if(!fn)ret.insert(s);
	}
	return ret;
}
mint dp[1<<20][2][3][3];
mint solve(string S)
{
	const int N=S.size();
	for(int i=0;i<=N;i++)for(int j=0;j<2;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++)dp[i][j][k][l]=0;
	if(S[0]!='x')dp[1][0][0][2]++;
	if(S[0]!='o')dp[1][1][0][2]++;
	for(int i=1;i<N;i++)
	{
		for(int j=0;j<2;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++)
		{
			if(S[i]!='x')
			{
				int nj=0;
				int nk=k,nl=l;
				if(j==nj)nl=min(nl+1,2);
				else
				{
					nl=0;
					if(l==1&&k==1);
					else if(l>=1)nk=0;
					else nk++;
				}
				if(nk<2)dp[i+1][nj][nk][nl]+=dp[i][j][k][l];
			}
			if(S[i]!='o')
			{
				int nj=1;
				int nk=k,nl=l;
				if(j==nj)nl=min(nl+1,2);
				else
				{
					nl=0;
					if(l==1&&k==1);
					else if(l>=1)nk=0;
					else nk++;
				}
				if(nk<2)dp[i+1][nj][nk][nl]+=dp[i][j][k][l];
			}
		}
	}
	mint ans=0;
	for(int j=0;j<2;j++)for(int k=0;k<3;k++)for(int l=0;l<3;l++)ans+=dp[N][j][k][l];
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	for(int N=1;N<=0;N++)
	{
		auto t=naive(N);
		cout<<"N = "<<N<<endl;
		for(int i=0;i<1<<N;i++)
		{
			string s(N,'_');
			for(int j=0;j<N;j++)s[j]=i>>j&1?'x':'o';
			mint v=solve(s);
			if(v.val()==0&&t.find(s)==t.end())continue;
			if(v.val()==1&&t.find(s)!=t.end())continue;
			cout<<s<<" "<<v.val()<<" "<<(t.find(s)!=t.end())<<endl;
			return 0;
		}
	}
	int N;string S;
	cin>>N>>S;
	cout<<solve(S).val()<<endl;
}
0