結果
問題 |
No.1646 Avoid Palindrome
|
ユーザー |
|
提出日時 | 2021-08-18 20:59:53 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,400 ms / 3,000 ms |
コード長 | 1,498 bytes |
コンパイル時間 | 550 ms |
コンパイル使用メモリ | 31,744 KB |
実行使用メモリ | 133,888 KB |
最終ジャッジ日時 | 2024-11-08 16:25:15 |
合計ジャッジ時間 | 51,907 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 40 |
ソースコード
#include <stdio.h> #define MOD 998244353 #define MAX 50005 int dp[MAX][26][26]; char s[MAX]; int i, j, a, b, c, d, n, ans; int main(void) { scanf("%d %s", &n, s); if (n == 1) { printf("%d\n", s[0] == '?' ? 26 : 1); return (0); } for (i = 0; i < 26; ++i) { for (j = 0; j < 26; ++j) { if (i == j) continue; if (s[0] != '?' && s[0] - 'a' != i) continue; if (s[1] != '?' && s[1] - 'a' != j) continue; ++dp[2][i][j]; } } for (i = 2; i < n; ++i) { if (s[i] == '?') { for (a = 0; a < 26; ++a) { for (b = 0; b < 26; ++b) { if (a == b) continue; for (c = 0; c < 26; ++c) { if (a == c || b == c) continue; dp[i+1][b][c] += dp[i][a][b]; dp[i+1][b][c] %= MOD; } } } } else { d = s[i] - 'a'; for (a = 0; a < 26; ++a) { if (d == a) continue; for (b = 0; b < 26; ++b) { if (a == b || d == b) continue; dp[i+1][b][d] += dp[i][a][b]; dp[i+1][b][d] %= MOD; } } } } ans = 0; for (i = 0; i < 26; ++i) { for (j = 0; j < 26; ++j) { ans += dp[n][i][j]; ans %= MOD; } } printf("%d\n", ans); }