結果
問題 |
No.2752 文字列の数え上げ mod 998244353
|
ユーザー |
|
提出日時 | 2024-05-10 23:48:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 723 bytes |
コンパイル時間 | 743 ms |
コンパイル使用メモリ | 80,120 KB |
最終ジャッジ日時 | 2025-02-21 13:24:28 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 TLE * 1 -- * 4 |
ソースコード
#include<iostream> #include<vector> #include<map> using namespace std; const int MOD = 998244353; map<long long, long long> mf, mg; //26^N long long g(long long N) { if (mg[N]) return mg[N]; if (N == 0) return 1; if (N == 1) return 26; if (N % 2 == 1) { return mg[N] = (26 * g(N - 1)) % MOD; } long long tmp = g(N / 2); return mg[N] = tmp * tmp % MOD; } long long f(long long L) { if (mf[L]) return mf[L]; if (L == 0) return 0; if (L == 1) return 26; if (L % 2 == 1) { return mf[L] = (26 + 26 * f(L - 1)) % MOD; } return mf[L] = (f(L / 2) + g(L / 2) * f(L / 2) % MOD) % MOD; } int main() { int T; cin >> T; while (T--) { long long L; cin >> L; cout << f(L) << endl; } }