結果
問題 | No.2131 Concon Substrings (COuNt Version) |
ユーザー |
![]() |
提出日時 | 2024-12-05 03:04:51 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,468 bytes |
コンパイル時間 | 1,826 ms |
コンパイル使用メモリ | 167,220 KB |
実行使用メモリ | 13,696 KB |
最終ジャッジ日時 | 2024-12-05 03:05:31 |
合計ジャッジ時間 | 38,902 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 TLE * 1 |
other | AC * 5 TLE * 11 |
ソースコード
#include<bits/stdc++.h> using namespace std; long long modinv(long long a, long long m) { long long b = m, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } u %= m; if (u < 0) u += m; return u; } long long combination_mp(long long n, long long k) { if (k > n) return 0; // kがnより大きい場合は0 if (k == 0 || k == n) return 1; // nC0 = nCn = 1 // 最適化:k を min(k, n-k) にして計算量を減らす k = min(k, n - k); long long result = 1; // nCk を逐次計算 for (long long i = 0; i < k; ++i) { result *= (n - i); result = result % 998244353; result *= modinv(i + 1,998244353); result = result % 998244353; } return result % 998244353; } long long pow_mp(long long x,long long y){//x^y mod 998244353 long long result = 1; for(long long i=0;i<y;i++){ result *= x; result = result % 998244353; } return result; } long long g(long long N,long long n){ long long result = 0; for(long long k=0;k<=N-3*n;k++){ result += ((pow_mp(25,N-3*n-k)*pow_mp(26,k)) % 998244353) * combination_mp(N-k-1,3*n-1) % 998244353; result = result % 998244353; } return result; } int main(){ long long N; cin >> N; long long res = 0; for(long long n=1;N-3*n>=0;n++){ res += g(N,n); res = res % 998244353; } cout << res << endl; }