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

提出ソース

結果

問題	No.1068 #いろいろな色 / Red and Blue and more various colors (Hard)
ユーザー	FF256grhy
提出日時	2020-05-29 23:16:45
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,364 ms / 3,500 ms
コード長	4,460 bytes
コンパイル時間	2,567 ms
コンパイル使用メモリ	211,568 KB
実行使用メモリ	63,252 KB
最終ジャッジ日時	2024-11-06 07:54:20
合計ジャッジ時間	27,533 ms
ジャッジサーバーID （参考情報）	judge5 / judge1

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,820 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,816 KB
testcase_03	AC	28 ms 6,820 KB
testcase_04	AC	16 ms 6,816 KB
testcase_05	AC	19 ms 6,816 KB
testcase_06	AC	16 ms 6,820 KB
testcase_07	AC	15 ms 6,816 KB
testcase_08	AC	18 ms 6,820 KB
testcase_09	AC	19 ms 6,816 KB
testcase_10	AC	9 ms 6,816 KB
testcase_11	AC	15 ms 6,820 KB
testcase_12	AC	9 ms 6,816 KB
testcase_13	AC	1,277 ms 63,128 KB
testcase_14	AC	1,275 ms 63,120 KB
testcase_15	AC	1,281 ms 63,252 KB
testcase_16	AC	1,364 ms 63,124 KB
testcase_17	AC	1,279 ms 63,252 KB
testcase_18	AC	1,272 ms 63,196 KB
testcase_19	AC	1,281 ms 63,124 KB
testcase_20	AC	1,273 ms 63,124 KB
testcase_21	AC	1,277 ms 63,124 KB
testcase_22	AC	1,280 ms 63,124 KB
testcase_23	AC	1,279 ms 63,124 KB
testcase_24	AC	1,279 ms 63,132 KB
testcase_25	AC	1,290 ms 63,124 KB
testcase_26	AC	1,273 ms 63,124 KB
testcase_27	AC	1,275 ms 63,124 KB
testcase_28	AC	1,287 ms 63,000 KB
testcase_29	AC	1,225 ms 63,120 KB
testcase_30	AC	1,230 ms 63,124 KB
testcase_31	AC	2 ms 6,816 KB

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

ソースコード

raw source code

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

#define bit(b, i) (((b) >> (i)) & 1)
#define PC __builtin_popcountll
#define BL(a) (a ? 64 - __builtin_clzll(a) : 0)

int main() {
	IN(int, n, q);
	vector<LL> a(n), b(q);
	cin >> a >> b;
	
	vector<vector<LL>> v(1 << BL(n - 1), { 1 });
	inc(i, n) { v[i] = { (a[i] - 1) % 998244353, 1 }; }
	
	NTT<998244353, 3> ntt;
	dec(k, BL(n - 1)) {
		inc(i, 1 << k) {
			v[i] = ntt.convolution(v[2 * i], v[2 * i + 1]);
		}
	}
	RF(e, b) { OUT(v[0][e]); }
}

yukicoder

結果

テストケース

ソースコード