結果
問題 |
No.2636 No Waiting in Vain
|
ユーザー |
|
提出日時 | 2024-02-19 20:50:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 33 ms / 2,000 ms |
コード長 | 2,474 bytes |
コンパイル時間 | 1,984 ms |
コンパイル使用メモリ | 196,916 KB |
最終ジャッジ日時 | 2025-02-19 16:28:18 |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 44 |
ソースコード
#include <bits/stdc++.h> using namespace std; long long mod = 998244353; //入力が必ずmod未満の時に使う. struct mint{ long long v = 0; mint(){} mint(int a){v = a;} mint(long long a){v = a;} mint(unsigned long long a){v = a;} long long val(){return v;} void modu(){v %= mod;} mint repeat2mint(long long a,long long b){ mint ret = 1,p = a; int Log = 60; if(b <= 2e9) Log = 30; for(int i=0; i<Log; i++){if(b&(1LL<<i)) ret *= p; p *= p;} return ret; }; mint operator+(mint b){return (v+b.v)%mod;} mint operator-(mint b){return (v-b.v+mod)%mod;} mint operator*(mint b){return v*b.v%mod;} mint operator/(mint b){ if(b.v == 0) assert(false); return v*(repeat2mint(b.v,mod-2)).v%mod; } void operator+=(mint b){v = (v+b.v)%mod;} void operator-=(mint b){v = (v-b.v+mod)%mod;} void operator*=(mint b){v = v*b.v%mod;} void operator/=(mint b){ if(b.v == 0) assert(false); v = v*repeat2mint(b.v,mod-2).v%mod; } void operator++(int){v = (v+1)%mod; return;} void operator--(int){v = (v-1+mod)%mod; return;} bool operator==(mint b){if(v == b.v) return true; else return false;} bool operator!=(mint b){if(v != b.v) return true; else return false;} bool operator>(mint b){if(v > b.v) return true; else return false;} bool operator>=(mint b){if(v >= b.v) return true; else return false;} bool operator<(mint b){if(v < b.v) return true; else return false;} bool operator<=(mint b){if(v <= b.v) return true; else return false;} mint pow(long long x){return repeat2mint(v,x);} mint inv(){return mint(1)/v;} }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N,K; cin >> N >> K; string s; cin >> s; vector<mint> fac(N+1,1),inv(N+1,1),facinv(N+1,1); for(int i=1; i<=N; i++) fac.at(i).v = fac.at(i-1).v*i %mod; for(int i=2; i<=N; i++) inv.at(i).v = mod-(mod/i*inv.at(mod%i).v %mod); for(int i=2; i<=N; i++) facinv.at(i).v = facinv.at(i-1).v*inv.at(i).v %mod; auto nCr = [&](int n, int r) -> mint { return fac.at(n)*facinv.at(r)*facinv.at(n-r); }; int ok = 0; for(int i=0; i<N; i++){ if(s.at(i) == 'N'){ ok++; if(i) if(s.at(i-1) == 'C') K--,ok--; } } K = max(K,0); K = ok-K; mint answer = 0; for(int i=1; i<=K; i++) answer += nCr(ok,i); cout << answer.v << endl; }