結果
問題 |
No.2636 No Waiting in Vain
|
ユーザー |
![]() |
提出日時 | 2024-02-22 00:16:05 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 17 ms / 2,000 ms |
コード長 | 826 bytes |
コンパイル時間 | 1,998 ms |
コンパイル使用メモリ | 194,916 KB |
最終ジャッジ日時 | 2025-02-19 18:41:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int N, K; string S; cin >> N >> K >> S; constexpr int mod = 998244353; int fact[300001], inv[300001], inv_fact[300001]; fact[0] = inv_fact[0] = 1; fact[1] = inv_fact[1] = inv[1] = 1; for (int i = 2; i <= 300000; ++i) { fact[i] = (long long)i * fact[i-1] % mod; inv[i] = (long long)(mod - inv[mod % i]) * (mod / i) % mod; inv_fact[i] = (long long)inv[i] * inv_fact[i-1] % mod; } int cnt{}; for (int i = 0; i < N; ++i) if (S[i] == 'N') { if (i == 0) ++cnt; else if (S[i-1] == 'C') --K; else ++cnt; } int ans{}; for (int k = 1; k <= cnt - max(K, 0); ++k) { ans += (long long)fact[cnt] * inv_fact[cnt-k] % mod * inv_fact[k] % mod; ans %= mod; } cout << ans << endl; }