結果
問題 |
No.2636 No Waiting in Vain
|
ユーザー |
![]() |
提出日時 | 2024-05-23 23:46:44 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 992 bytes |
コンパイル時間 | 1,898 ms |
コンパイル使用メモリ | 169,360 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-12-20 19:07:50 |
合計ジャッジ時間 | 3,401 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | WA * 44 |
ソースコード
#include<bits/stdc++.h> using namespace std; vector<int> decimal_to_binary(long long N){ vector<int> result; while(N != 0){ result.insert(result.begin(),N%2); N = N/2; } return result; } //a^n mod pの高速計算 //O(log p) long long calc_modulo_p(long long a,long long n,long long p){ a = a%p; n = n%(p-1); vector<int> binary = decimal_to_binary(n); long long x = a; long long result = 1; int N = binary.size(); for(int i=0;i<N;i++){ if(binary[N-1-i] == 1){ result = (result * x)%p; } x = (x*x)%p; } return result; } int main(){ long long N,K; cin >> N >> K; char s[N]; scanf("%s",&s); long long good_day = 0; for(int i=0;i<N;i++){ if(s[i] == 'C'){ i++; continue; } if(s[i] == 'N'){ good_day++; } } good_day = good_day-K; cout << good_day << endl; if(good_day <= 0){ cout << 0 << endl; } else { cout << calc_modulo_p(2,good_day,998244353) << endl; } }