結果

問題 No.3098 Linear Reversi
コンテスト
ユーザー ygussany
提出日時 2025-03-17 19:36:13
言語 C
(gcc 15.2.0)
コンパイル:
gcc-15 -O2 -DONLINE_JUDGE -o a.out _filename_ -lm
実行:
./a.out
結果
AC  
実行時間 36 ms / 4,000 ms
コード長 1,516 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 155 ms
コンパイル使用メモリ 40,264 KB
最終ジャッジ日時 2026-02-22 13:17:06
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <stdio.h>

const int Mod = 998244353;

long long solve(int N, char S[])
{
	int i, j, k, l, cur, prev;
	long long dp[2][2][2][4] = {};
	if (S[0] != 'x') dp[0][0][0][3] = 1;
	if (S[0] != 'o') dp[0][0][1][3] = 1;
	for (i = 1, cur = 1, prev = 0; i < N; i++, cur ^= 1, prev ^= 1) {
		for (j = 0; j < 2; j++) for (k = 0; k < 2; k++) for (l = 1; l < 4; l++) dp[cur][j][k][l] = 0;
		if (S[i] != 'x') {
			dp[cur][0][0][1] += dp[prev][0][1][2] + dp[prev][0][1][3] + dp[prev][1][1][3];
			dp[cur][0][0][2] += dp[prev][0][0][1];
			dp[cur][0][0][3] += dp[prev][0][0][2] + dp[prev][0][0][3];
			dp[cur][1][0][1] += dp[prev][0][1][1] + dp[prev][1][1][2];
			dp[cur][1][0][2] += dp[prev][1][0][1];
			dp[cur][1][0][3] += dp[prev][1][0][2] + dp[prev][1][0][3];
		}
		if (S[i] != 'o') {
			dp[cur][0][1][1] += dp[prev][0][0][2] + dp[prev][0][0][3] + dp[prev][1][0][3];
			dp[cur][0][1][2] += dp[prev][0][1][1];
			dp[cur][0][1][3] += dp[prev][0][1][2] + dp[prev][0][1][3];
			dp[cur][1][1][1] += dp[prev][0][0][1] + dp[prev][1][0][2];
			dp[cur][1][1][2] += dp[prev][1][1][1];
			dp[cur][1][1][3] += dp[prev][1][1][2] + dp[prev][1][1][3];
		}
		for (j = 0; j < 2; j++) for (k = 0; k < 2; k++) for (l = 0; l < 4; l++) dp[cur][j][k][l] %= Mod;
	}
	
	long long ans = 0;
	for (j = 0; j < 2; j++) for (k = 0; k < 2; k++) for (l = 1; l < 4; l++) ans += dp[prev][j][k][l];
	return ans % Mod;
}

int main()
{
	int N;
	char S[1000001];
	scanf("%d", &N);
	scanf("%s", S);
	printf("%lld\n", solve(N, S));
	fflush(stdout);
	return 0;
}
0