結果

問題 No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー momoharamomohara
提出日時 2020-05-30 00:32:04
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,383 bytes
コンパイル時間 2,125 ms
コンパイル使用メモリ 181,328 KB
実行使用メモリ 4,384 KB
最終ジャッジ日時 2023-08-06 06:58:54
合計ジャッジ時間 8,518 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,376 KB
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 TLE -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);++i)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);--i)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
//constexpr long long MOD = (ll) 1e9 + 7;
constexpr long long MOD = 998244353LL;
using ld=long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct Edge {
	ll to, rev;
    long double cap;
	Edge(ll _to, long double _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

void add_edge(Graph& G, ll from, ll to, long double cap, bool revFlag, long double revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

ll mod_pow(ll x, ll n, ll mod) {
 ll res = 1LL;
 while (n > 0) {
  if (n & 1) res = res * x % mod;
  x = x * x % mod;
  n >>= 1;
 }
 return res;
}

ll mod_inv(ll x, ll mod) {
 return mod_pow(x, mod - 2, mod);
}

ll _garner(Array& xs, Array& mods) {
 int M = xs.size();

 Array coeffs(M, 1), constants(M, 0);

 for (int i = 0; i < M - 1; ++i) {
  ll mod_i = mods[i];
  // coffs[i] * v + constants[i] == mr[i].val (mod mr[i].first) ������
  ll v = (xs[i] - constants[i] + mod_i) % mod_i;
  v = (v * mod_pow(coeffs[i], mod_i - 2, mod_i)) % mod_i;

  for (int j = i + 1; j < M; j++) {
   ll mod_j = mods[j];
   constants[j] = (constants[j] + coeffs[j] * v) % mod_j;
   coeffs[j] = (coeffs[j] * mod_i) % mod_j;
  }
 }

 return constants.back();
}

template<typename T>
inline void bit_reverse(vector<T>& 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]);
 }
}

template<long long mod, long long primitive_root>
class NTT {
public:
 long long get_mod() { return mod; }

 void _ntt(vector<long long>& a, int sign) {
  const int n = a.size();
  assert((n ^ (n & -n)) == 0); //n = 2^k

  const long long g = primitive_root; // g is primitive root of mod

  long long tmp = (mod - 1) * mod_pow(n, mod - 2, mod) % mod; // -1/n
  long long h = mod_pow(g, tmp, mod); // ^n��g
  if (sign == -1) h = mod_pow(h, mod - 2, mod);

  bit_reverse(a);

  for (int m = 1; m < n; m <<= 1) {
   const int m2 = 2 * m;
   long long _base = mod_pow(h, n / m2, mod);
   long long _w = 1;
   for (int x = 0; x < m; ++x) {
    for (int s = x; s < n; s += m2) {
     long long u = a[s];
     long long 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<long long>& input) {
  _ntt(input, 1);
 }
 void intt(vector<long long>& input) {
  _ntt(input, -1);

  const long long n_inv = mod_pow(input.size(), mod - 2, mod);
  for (auto& x : input) x = (x * n_inv) % mod;
 }

 //畳み込み演算を行う
 vector<long long> convolution(const vector<long long>& a, const vector<long long>& b) {
  int result_size = a.size() + b.size() - 1;
  int n = 1; while (n < result_size) n <<= 1;

  vector<long long> _a = a, _b = b;
  _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(result_size);
  return _a;
 }
};

vector<long long> convolution_ntt(vector<long long>& a, vector<long long>& b, long long mod = 1224736769LL) {
 for (auto& x : a) x %= mod;
 for (auto& x : b) x %= mod;

 ll maxval = max(a.size(), b.size()) * *max_element(a.begin(), a.end()) * *max_element(b.begin(), b.end());
 if (maxval < 1224736769) {
  NTT<1224736769, 3> ntt3;
  return ntt3.convolution(a, b);
 }

 NTT<167772161, 3> ntt1;
 NTT<469762049, 3> ntt2;
 NTT<1224736769, 3> ntt3;

 vector<long long> x1 = ntt1.convolution(a, b);
 vector<long long> x2 = ntt2.convolution(a, b);
 vector<long long> x3 = ntt3.convolution(a, b);

 vector<long long> ret(x1.size());
 vector<long long> mods{ 167772161, 469762049, 1224736769, mod };
 for (int i = 0; i < x1.size(); ++i) {
  vector<long long> xs{ x1[i], x2[i], x3[i], 0 };
  ret[i] = _garner(xs, mods);
 }

 return ret;
}

void solve(){
    ll n,q;
    cin>>n>>q;
    Array a(n),b(q);
    REP(i,n) cin>>a[i];
    REP(i,q) cin>>b[i];

    auto solve = [&](auto && self,int l, int r)->vec<ll>{
        if(r-l==1) return vec<ll>({(a[l]-1)%MOD,1});
        int m=l+r>>1;
        auto L = self(self,l,m);
        auto R = self(self,m,r);
        return convolution_ntt(L, R, MOD);
    };

    auto result = solve(solve,0,n);
    
    REP(i,q){
        cout<<result[b[i]]%MOD<<en;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	
	solve();
	//ll t;cin>>t;REP(i,t) solve();

    return 0;
}
0