結果

問題 No.3098 Linear Reversi
コンテスト
ユーザー 👑 ygussany
提出日時 2025-03-17 19:36:13
言語 C
(gcc 13.3.0)
結果
AC  
実行時間 26 ms / 4,000 ms
コード長 1,516 bytes
コンパイル時間 1,718 ms
コンパイル使用メモリ 26,880 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-04-06 15:01:09
合計ジャッジ時間 1,917 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 37
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘main’:
main.c:41:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   41 |         scanf("%d", &N);
      |         ^~~~~~~~~~~~~~~
main.c:42:9: warning: ignoring return value of ‘scanf’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   42 |         scanf("%s", S);
      |         ^~~~~~~~~~~~~~

ソースコード

diff # 

#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