結果

問題 No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
コンテスト
ユーザー どらら
提出日時 2020-05-30 12:40:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 868 ms / 3,500 ms
コード長 2,967 bytes
コンパイル時間 2,302 ms
コンパイル使用メモリ 176,948 KB
実行使用メモリ 14,160 KB
最終ジャッジ日時 2024-11-07 10:31:53
合計ジャッジ時間 19,806 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;



template<ll mod, ll primitive_root>
class NTT {
  void bit_reverse(vector<ll>& a){
    int N = a.size();
    int i = 0;
    for(int j=1; j<N-1; j++){
      for(int k=N>>1; k>(i^=k); k>>=1);
      if(j < i) swap(a[i], a[j]);
    }
  }
  ll extgcd(ll a, ll b, ll &x, ll &y){
    ll d = a;
    if(b!=0){
      d = extgcd(b,a%b,y,x);
      y -= (a/b)*x;
    }else{
      x = 1; y = 0;
    }
    return d;
  }
  ll mod_inv(ll a){
    ll x, y;
    extgcd(a, mod, x, y);
    return (mod + x % mod) % mod;
  }
  ll mod_pow(ll x, ll n){
    if(n==0) return 1;
    ll res = mod_pow(x * x % mod, n / 2);
    if(n & 1) res = res * x % mod;
    return res;
  }
  
  void _calc(vector<ll>& a, int sign){
    int N = a.size();
    ll g = primitive_root;

    ll tmp = (mod - 1) * mod_inv(N) % mod;
    ll h = mod_pow(g, tmp);
    if(sign == -1) h = mod_inv(h);

    bit_reverse(a);
    
    for(int m=1; m<N; m<<=1){
      ll _base = mod_pow(h, N/(2*m));
      ll _w = 1;
      for(int x=0; x<m; x++){
        for(int s=x; s<N; s+=(2*m)){
          ll u = a[s];
          ll d = (a[s+m] * _w) % mod;
          a[s] = (u+d) % mod;
          a[s+m] = (u-d+mod) % mod;
        }
        _w = (_w * _base) % mod;
      }
    }
  }

  void ntt(vector<ll>& in){ _calc(in, 1); }
  void intt(vector<ll>& in){
    _calc(in, -1);
    ll n_inv = mod_inv(in.size());
    for(int i=0; i<in.size(); i++){
      in[i] = (in[i] * n_inv) % mod;
    }
  }

public:
  NTT(){}

  long long get_mod() const { return mod; }

  vector<ll> conv(const vector<ll>& a, const vector<ll>& b){
    vector<ll> _a = a, _b = b;
    int m = a.size() + b.size() - 1;
    int n = 1; while(n < m) n <<= 1;
    _a.resize(n, 0);
    _b.resize(n, 0);
    ntt(_a);
    ntt(_b);
    for(int i=0; i<n; i++) _a[i] = (_a[i] * _b[i]) % mod;
    intt(_a);
    _a.resize(m);
    return _a;
  }
};

NTT<998244353,3> ntt;

vector<ll> solve(const vector<ll>& v, int l, int m, int r){
  if(l == m) return vector<ll>{1, v[l]-1};

  vector<ll> lhs = solve(v, l, (l+m)/2, m);
  vector<ll> rhs = solve(v, m, (m+r)/2, r);
  return ntt.conv(lhs, rhs);
}


int main(){
  int N, Q;
  cin >> N >> Q;
  vector<ll> v;
  rep(i,N){
    ll a;
    cin >> a;
    v.push_back(a);
  }

  vector<ll> ret = solve(v, 0, v.size()/2, v.size());
  reverse(ALLOF(ret));

  rep(i,Q){
    int b;
    cin >> b;
    cout << ret[b] << endl;
  }

  return 0;
}
0