結果
問題 | No.1068 #いろいろな色 / Red and Blue and more various colors (Hard) |
ユーザー |
![]() |
提出日時 | 2020-05-29 23:16:11 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 471 ms / 3,500 ms |
コード長 | 2,627 bytes |
コンパイル時間 | 1,145 ms |
コンパイル使用メモリ | 89,688 KB |
実行使用メモリ | 17,204 KB |
最終ジャッジ日時 | 2024-11-06 07:52:13 |
合計ジャッジ時間 | 11,123 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 29 |
ソースコード
#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; ll N, Q; ll A[200000], B[10000]; #define root 3 ll add(const ll x, const ll y) { return (x + y < MOD) ? x + y : x + y - MOD; } ll sub(const ll x, const ll y) { return (x >= y) ? (x - y) : (MOD - y + x); } ll mul(const ll x, const ll y) { return (unsigned long long)x * y % MOD; } ll mod_pow(ll x, ll n) { ll res = 1; while(n > 0){ if(n & 1){ res = mul(res, x); } x = mul(x, x); n >>= 1; } return res; } ll inverse(const ll x) { return mod_pow(x, MOD - 2); } void ntt(vector<ll>& a, const bool rev = false) { ll i, j, k, l, p, q, r, s; const ll size = a.size(); if(size == 1) return; vector<ll> b(size); r = rev ? (MOD - 1 - (MOD - 1) / size) : (MOD - 1) / size; s = mod_pow(root, r); vector<ll> kp(size / 2 + 1, 1); for(i = 0; i < size / 2; ++i) kp[i + 1] = mul(kp[i], s); for(i = 1, l = size / 2; i < size; i <<= 1, l >>= 1){ for(j = 0, r = 0; j < l; ++j, r += i){ for(k = 0, s = kp[i * j]; k < i; ++k){ p = a[k + r], q = a[k + r + size / 2]; b[k + 2 * r] = add(p, q); b[k + 2 * r + i] = mul(sub(p, q), s); } } swap(a, b); } if(rev){ s = inverse(size); for(i = 0; i < size; i++){ a[i] = mul(a[i], s); } } } vector<ll> convolute(const vector<ll>& a, const vector<ll>& b) { const ll size = (ll)a.size() + (ll)b.size() - 1; ll t = 1; while(t < size){ t <<= 1; } vector<ll> A(t, 0), B(t, 0); for(ll i = 0; i < (ll)a.size(); i++){ A[i] = a[i]; } for(ll i = 0; i < (ll)b.size(); i++){ B[i] = b[i]; } ntt(A), ntt(B); for (ll i = 0; i < t; i++){ A[i] = mul(A[i], B[i]); } ntt(A, true); A.resize(size); return A; } vector<ll> calc(ll l, ll r){ if(l == r){ vector<ll> ans; ans.push_back(A[l]-1); ans.push_back(1); return ans; } ll c = (l+r)/2; auto vl = calc(l, c); auto vr = calc(c+1, r); auto ans = convolute(vl, vr); return ans; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout << setprecision(10) << fixed; cin >> N >> Q; for(ll i = 0; i < N; i++) { cin >> A[i]; A[i]%= MOD; } for(ll i = 0; i < Q; i++) cin >> B[i]; auto conv = calc(0, N-1); for(ll i = 0; i < Q; i++) { cout << conv[B[i]] << endl; } }