結果

問題 No.3371 Add Insert Operations
コンテスト
ユーザー Naru820
提出日時 2025-10-25 21:48:47
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 838 bytes
コンパイル時間 2,768 ms
コンパイル使用メモリ 276,888 KB
実行使用メモリ 15,848 KB
最終ジャッジ日時 2025-11-17 20:33:27
合計ジャッジ時間 5,426 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 25 RE * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define popc(x) __builtin_popcount(x)
using namespace std;
const int N=1e6+5,mod=998244353;
inline void add(int &x,int v){ x=(x+v)%mod; }
int n,a[N],s[N],f[N],nxt[N][8],tmp[8];
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	string str;
	cin>>str;
	n = str.size();
	for(int i=1;i<=n;i++) a[i]=(str[i-1]-'A');
	int fl=1;
	for(int i=1;i<=n;i++) fl&=(a[i]==a[1]);
	if(fl){
		cout<<1<<"\n";
		return 0;
	}
	for(int i=1;i<=n;i++){
		s[i]=s[i-1]^(1<<a[i]);
	}
	for(int k=0;k<8;k++) nxt[n+1][k]=n+1;
	for(int i=n;i>=1;i--){
		for(int k=0;k<8;k++) nxt[i][k]=nxt[i+1][k];
		nxt[i][s[i]]=i;
	}
	for(int i=n+1,j=n+1;i>=1;i--){
		if(((s[i-1]^s[n])==0 || (s[i-1]^s[n])==7) && i>1) f[i]=1;
		for(int k=1;k<4;k++){
			int x=(k^s[i-1]),y=(7^k^s[i-1]);
			add(f[i],f[min(nxt[i][x],nxt[i][y])+1]);
		}
		
	}
	cout<<f[1]<<"\n";
}
0