結果

問題 No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー どららどらら
提出日時 2020-05-30 12:27:10
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 4,532 bytes
コンパイル時間 2,858 ms
コンパイル使用メモリ 183,772 KB
実行使用メモリ 5,712 KB
最終ジャッジ日時 2024-04-25 00:50:51
合計ジャッジ時間 13,408 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'll Garner::mod_inv(ll, ll)':
main.cpp:108:53: warning: no return statement in function returning non-void [-Wreturn-type]
  108 |   ll mod_inv(ll x, ll mod){ mod_pow(x, mod-2, mod); }
      |                                                     ^

ソースコード

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){ 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 = 1224736769LL){
    for(int i=0; i<a.size(); i++) a[i] %= mod;
    for(int i=0; i<b.size(); i++) b[i] %= mod;
    
    ll mx = max(a.size(), b.size());
    mx *= (*max_element(a.begin(), a.end()));
    mx *= (*max_element(b.begin(), b.end()));
    if(mx < 1224736769LL){
      NTT<1224736769LL, 3> ntt3;
      return ntt3.conv(a, b);
    }
    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{167772161, 469762049, 1224736769, 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, 998244353LL);
}


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