結果
問題 |
No.2636 No Waiting in Vain
|
ユーザー |
|
提出日時 | 2024-05-07 13:34:57 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,079 bytes |
コンパイル時間 | 1,634 ms |
コンパイル使用メモリ | 169,508 KB |
実行使用メモリ | 17,608 KB |
最終ジャッジ日時 | 2024-11-30 06:42:28 |
合計ジャッジ時間 | 59,764 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 25 TLE * 19 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define MOD 998244353 using ll = long long int; int mod_div(int x, int y) { //return (long long)x * mod_inv(y) % MOD; int z = MOD, u = 1, v = 0; while (z) { int t = y / z; y -= t * z; swap(y, z); u -= t * v; swap(u, v); } u %= MOD; if (u < 0) u += MOD; return (long long)x * u % MOD; } int mod_factorial (int x) { int ret = 1; while (x > 1) { ret = ((ll)ret * (ll)x) % MOD; x--; } return ret; } int main() { int N, K; cin >> N >> K; string S; cin >> S; int n = 0, nn = 0; rep(i, N) { if (S[i] == 'N') { if (i == 0) n++; else if (S[i-1] != 'C') n++; } if (S[i] == 'N') nn++; } int ans = 0; // nCr = nPr / r! = n! / (n-r)!*r! int nu = mod_factorial(n); rep(i, nn - K) { if (i+1 > n) break; int de = ((ll)mod_factorial(n-(i+1))* (ll)mod_factorial(i+1)) % MOD; int cnr = mod_div(nu, de) % MOD; ans = ((ll)ans + (ll)cnr) % MOD; } cout << ans << endl; return 0; }