#489352 (C++17) No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)

提出ソース

結果

問題	No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー	IKyopro
提出日時	2020-05-30 00:37:37
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	5,385 bytes
コンパイル時間	2,777 ms
コンパイル使用メモリ	217,708 KB
実行使用メモリ	15,540 KB
最終ジャッジ日時	2024-11-06 10:03:43
合計ジャッジ時間	9,223 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 13,644 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,820 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	--	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

yukicoder

結果

テストケース

ソースコード