結果

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

ソースコード

diff # 

#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;
  }
};

class Garner {
  ll mod_inv(ll x, ll mod){ return mod_pow(x, mod-2, mod); }
  ll mod_pow(ll x, ll n, ll mod){
    if(n==0) return 1;
    ll res = mod_pow(x * x % mod, n / 2, mod);
    if(n & 1) res = res * x % mod;
    return res;
  }
  ll garner(vector<ll>& xs, vector<ll>& mods){
    int M = xs.size();
    vector<ll> coefs(M, 1), con(M, 0);
    for(int i=0; i<M-1; i++){
      ll mod_i = mods[i];
      ll v = (xs[i] - con[i] + mod_i) % mod_i;
      v = (v * mod_inv(coefs[i], mod_i)) % mod_i;
      for(int j=i+1; j<M; j++){
        ll mod_j = mods[j];
        con[j] = (con[j] + coefs[j] * v) % mod_j;
        coefs[j] = (coefs[j] * mod_i) % mod_j;
      }
    }
    return con[con.size()-1];
  }
public:
  vector<ll> conv(vector<ll>& a, vector<ll>& b, ll mod){
    for(int i=0; i<a.size(); i++) a[i] %= mod;
    for(int i=0; i<b.size(); i++) b[i] %= mod;
    
    NTT<167772161LL, 3> ntt1;
    NTT<469762049LL, 3> ntt2;
    NTT<1224736769LL, 3> ntt3;
    
    vector<ll> x1 = ntt1.conv(a, b);
    vector<ll> x2 = ntt2.conv(a, b);
    vector<ll> x3 = ntt3.conv(a, b);
    
    vector<ll> ret(x1.size());
    vector<ll> mods{167772161LL, 469762049LL, 1224736769L, mod};
    for(int i=0; i<x1.size(); i++){
      vector<ll> xs{x1[i], x2[i], x3[i], 0};
      ret[i] = garner(xs, mods);
    }
    return ret;
  }
};

Garner garner;

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 garner.conv(lhs, rhs, 998244353);
}


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