結果
問題 | No.1068 #いろいろな色 / Red and Blue and more various colors (Hard) |
ユーザー | FF256grhy |
提出日時 | 2020-05-29 23:12:37 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,205 ms / 3,500 ms |
コード長 | 4,328 bytes |
コンパイル時間 | 2,057 ms |
コンパイル使用メモリ | 204,576 KB |
実行使用メモリ | 65,272 KB |
最終ジャッジ日時 | 2024-04-24 01:08:50 |
合計ジャッジ時間 | 35,171 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 706 ms
49,008 KB |
testcase_01 | AC | 717 ms
49,024 KB |
testcase_02 | AC | 709 ms
48,960 KB |
testcase_03 | AC | 726 ms
48,648 KB |
testcase_04 | AC | 718 ms
48,340 KB |
testcase_05 | AC | 710 ms
49,156 KB |
testcase_06 | AC | 742 ms
49,188 KB |
testcase_07 | AC | 712 ms
48,076 KB |
testcase_08 | AC | 704 ms
49,160 KB |
testcase_09 | AC | 712 ms
48,296 KB |
testcase_10 | AC | 714 ms
49,100 KB |
testcase_11 | AC | 706 ms
48,048 KB |
testcase_12 | AC | 707 ms
49,036 KB |
testcase_13 | AC | 1,169 ms
65,268 KB |
testcase_14 | AC | 1,148 ms
65,264 KB |
testcase_15 | AC | 1,205 ms
65,144 KB |
testcase_16 | AC | 1,153 ms
65,140 KB |
testcase_17 | AC | 1,169 ms
65,136 KB |
testcase_18 | AC | 1,146 ms
65,144 KB |
testcase_19 | AC | 1,156 ms
65,272 KB |
testcase_20 | AC | 1,170 ms
65,140 KB |
testcase_21 | AC | 1,142 ms
65,268 KB |
testcase_22 | AC | 1,157 ms
65,140 KB |
testcase_23 | AC | 1,149 ms
65,268 KB |
testcase_24 | AC | 1,171 ms
65,140 KB |
testcase_25 | AC | 1,185 ms
65,140 KB |
testcase_26 | AC | 1,157 ms
65,268 KB |
testcase_27 | AC | 1,161 ms
65,264 KB |
testcase_28 | AC | 1,202 ms
65,144 KB |
testcase_29 | AC | 1,107 ms
65,140 KB |
testcase_30 | AC | 1,106 ms
65,220 KB |
testcase_31 | AC | 705 ms
49,188 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; // https://math314.hateblo.jp/entry/2015/05/07/014908 typedef long long ll; typedef pair<int, int> Pii; #define FOR(i,n) for(int i = 0; i < (n); i++) #define sz(c) ((int)(c).size()) #define ten(x) ((int)1e##x) template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; } template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; } ll mod_pow(ll a, ll n, ll mod) { ll ret = 1; ll p = a % mod; while (n) { if (n & 1) ret = ret * p % mod; p = p * p % mod; n >>= 1; } return ret; } template<int mod, int primitive_root> class NTT { public: int get_mod() const { return mod; } void _ntt(vector<ll>& a, int sign) { const int n = sz(a); assert((n ^ (n&-n)) == 0); //n = 2^k const int g = 3; //g is primitive root of mod int h = (int)mod_pow(g, (mod - 1) / n, mod); // h^n = 1 if (sign == -1) h = (int)mod_inv(h, mod); //h = h^-1 % mod //bit reverse 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]); } for (int m = 1; m < n; m *= 2) { const int m2 = 2 * m; const ll base = mod_pow(h, n / m2, mod); ll w = 1; FOR(x, m) { for (int s = x; s < n; s += m2) { ll u = a[s]; ll d = a[s + m] * w % mod; a[s] = u + d; if (a[s] >= mod) a[s] -= mod; a[s + m] = u - d; if (a[s + m] < 0) a[s + m] += mod; } w = w * base % mod; } } for (auto& x : a) if (x < 0) x += mod; } void ntt(vector<ll>& input) { _ntt(input, 1); } void intt(vector<ll>& input) { _ntt(input, -1); const int n_inv = mod_inv(sz(input), mod); for (auto& x : input) x = x * n_inv % mod; } // 畳み込み演算を行う vector<ll> convolution(const vector<ll>& a, const vector<ll>& b){ int ntt_size = 1; while (ntt_size < sz(a) + sz(b)) ntt_size *= 2; vector<ll> _a = a, _b = b; _a.resize(ntt_size); _b.resize(ntt_size); ntt(_a); ntt(_b); FOR(i, ntt_size){ (_a[i] *= _b[i]) %= mod; } intt(_a); return _a; } }; // ---- ---- using LL = long long int; #define incID(i, l, r) for(int i = (l) ; i < (r); ++i) #define decID(i, l, r) for(int i = (r) - 1; i >= (l); --i) #define incII(i, l, r) for(int i = (l) ; i <= (r); ++i) #define decII(i, l, r) for(int i = (r) ; i >= (l); --i) #define inc(i, n) incID(i, 0, n) #define dec(i, n) decID(i, 0, n) #define inc1(i, n) incII(i, 1, n) #define dec1(i, n) decII(i, 1, n) #define inID(v, l, r) ((l) <= (v) && (v) < (r)) #define inII(v, l, r) ((l) <= (v) && (v) <= (r)) #define PB push_back #define EB emplace_back #define MP make_pair #define MT make_tuple #define FI first #define SE second #define FR front() #define BA back() #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() auto setmin = [](auto & a, auto b) { return (b < a ? a = b, true : false); }; auto setmax = [](auto & a, auto b) { return (b > a ? a = b, true : false); }; auto setmineq = [](auto & a, auto b) { return (b <= a ? a = b, true : false); }; auto setmaxeq = [](auto & a, auto b) { return (b >= a ? a = b, true : false); }; #define SI(v) static_cast<int>(v.size()) #define RF(e, v) for(auto & e: v) #define until(e) while(! (e)) #define if_not(e) if(! (e)) #define ef else if #define UR assert(false) #define IN(T, ...) T __VA_ARGS__; IN_(__VA_ARGS__); void IN_() { }; template<typename T, typename ... U> void IN_(T & a, U & ... b) { cin >> a; IN_(b ...); }; template<typename T > void OUT(T && a ) { cout << a << endl; } template<typename T, typename ... U> void OUT(T && a, U && ... b) { cout << a << " "; OUT(b ...); } // ---- ---- template<typename T> istream & operator>>(istream & s, vector<T> & v) { RF(e, v) { s >> e; } return s; } template<typename T> ostream & operator<<(ostream & s, vector<T> const & v) { inc(i, SI(v)) { s << (i == 0 ? "" : " ") << v[i]; } return s; } int main() { IN(int, n, q); vector<LL> a(n), b(q); cin >> a >> b; vector<vector<LL>> v(1 << 18, { 1 }); inc(i, n) { v[i] = { (a[i] - 1) % 998244353, 1 }; } NTT<998244353, 3> ntt; dec(k, 18) { inc(i, 1 << k) { v[i] = ntt.convolution(v[2 * i], v[2 * i + 1]); } } RF(e, b) { OUT(v[0][e]); } }