結果
問題 | No.1066 #いろいろな色 / Red and Blue and more various colors (Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-29 21:56:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 72 ms / 2,000 ms |
コード長 | 953 bytes |
コンパイル時間 | 859 ms |
コンパイル使用メモリ | 83,124 KB |
実行使用メモリ | 6,824 KB |
最終ジャッジ日時 | 2024-11-06 04:14:57 |
合計ジャッジ時間 | 2,138 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 24 |
ソースコード
#include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <queue> #include <set> #include <map> using namespace std; typedef long long ll; const ll MOD = 998244353; int N, Q; ll A[10000], B[10000]; ll dp[2][6005]; void init(){ dp[0][0] = 1; for(int i = 1; i <= N; i++){ for(int j = 0; j <= N; j++){ dp[i%2][j] = 0; } for(int j = 0; j <= i-1; j++){ // 1 dp[i%2][(j+1)] += dp[(i-1)%2][j]; dp[i%2][(j+1)] %= MOD; // 1 以外 dp[i%2][j] += dp[(i-1)%2][j]*(A[i-1]-1); dp[i%2][j] %= MOD; } } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> N >> Q; for(int i = 0; i < N; i++) cin >> A[i]; for(int i = 0; i < Q; i++) cin >> B[i]; init(); for(int i = 0; i < Q; i++){ cout << dp[N%2][B[i]] << endl; } }