結果

問題 No.1307 Rotate and Accumulate
ユーザー tkmst201tkmst201
提出日時 2020-12-30 12:45:21
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 100 ms / 5,000 ms
コード長 4,951 bytes
コンパイル時間 1,970 ms
コンパイル使用メモリ 208,564 KB
実行使用メモリ 7,392 KB
最終ジャッジ日時 2024-10-07 03:18:14
合計ジャッジ時間 4,674 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 2 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 2 ms
5,248 KB
testcase_06 AC 2 ms
5,248 KB
testcase_07 AC 2 ms
5,248 KB
testcase_08 AC 70 ms
6,936 KB
testcase_09 AC 81 ms
6,932 KB
testcase_10 AC 50 ms
5,364 KB
testcase_11 AC 40 ms
5,440 KB
testcase_12 AC 50 ms
5,248 KB
testcase_13 AC 12 ms
5,248 KB
testcase_14 AC 25 ms
5,248 KB
testcase_15 AC 90 ms
7,392 KB
testcase_16 AC 100 ms
7,268 KB
testcase_17 AC 91 ms
7,268 KB
testcase_18 AC 89 ms
7,216 KB
testcase_19 AC 93 ms
7,268 KB
testcase_20 AC 92 ms
7,268 KB
testcase_21 AC 1 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) begin(v),end(v)
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using pii = pair<int, int>;
constexpr ll INF = 1ll<<30;
constexpr ll longINF = 1ll<<60;
constexpr ll MOD = 998244353;
constexpr bool debug = false;
//---------------------------------//

#include <cassert>
#include <utility>

namespace tk {
template<typename T>
T gcd(T a, T b) {
	assert(a >= 0);
	assert(b >= 0);
	while (b != 0) {
		T t = a % b;
		a = b; b = t;
	}
	return a;
}

template<typename T>
T lcm(T a, T b) {
	assert(a >= 0);
	assert(b >= 0);
	if (a == 0 || b == 0) return 0;
	return a / gcd(a, b) * b;
}

template<typename T>
T ext_gcd(const T & a, T & x, const T & b, T & y) {
	assert(a > 0);
	assert(b > 0);
	T a0 = a, a1 = 1, a2 = 0, b0 = b, b1 = 0, b2 = 1;
	while (b0 > 0) {
		T q = a0 / b0, r = a0 % b0;
		T nb1 = a1 - q * b1, nb2 = a2 - q * b2;
		a0 = b0; b0 = r;
		a1 = b1; b1 = nb1;
		a2 = b2; b2 = nb2;
	}
	x = a1;
	y = a2;
	return a0;
}

template<typename T>
T mod_pow(T x, T n, const T & mod) {
	assert(mod > 0);
	assert(n >= 0);
	x = (x % mod + mod) % mod;
	T res = 1 % mod;
	while (n > 0) {
		if (n & 1) res = res * x % mod;
		x = x * x % mod;
		n >>= 1;
	}
	return res;
}

template<typename T>
T mod_inv(const T & x, const T & mod) {
	assert(x > 0);
	assert(mod > 0);
	T a, b;
	T g = ext_gcd(x, a, mod, b);
	assert(g == 1);
	return (a % mod + mod) % mod;
}

template<typename T>
std::pair<T, T> chinese_remainder(T b1, T m1, T b2, T m2) {
	assert(m1 > 0);
	assert(m2 > 0);
	if (m1 < m2) { std::swap(b1, b2); std::swap(m1, m2); }
	b1 = (b1 % m1 + m1) % m1;
	b2 = (b2 % m2 + m2) % m2;
	
	T x, y;
	T g = ext_gcd(m1, x, m2, y);
	const T pm2 = m2 / g;
	x = (x % pm2 + pm2) % pm2;
	
	if ((b2 - b1) % g != 0) return {0, 0};
	const T t = ((b2 - b1) / g % pm2 + pm2) % pm2 * x % pm2;
	return {b1 + t * m1, m1 * pm2};
}
} // namespace tk

#include <vector>
#include <utility>
#include <cassert>
#include <cstdint>

template<int MOD, int PRIMITIVE_ROOT>
struct NumberTheoreticTransform {
public:
	using value_type = long long;
	using size_type = std::uint_fast32_t;
	static_assert(MOD > 0);
	
	template<typename T>
	static std::vector<T> multiply(const std::vector<T> & A, const std::vector<T> & B) {
		if (A.empty() || B.empty()) return {};
		size_type n_ = A.size() + B.size() - 1;
		size_type n = 1;
		while (n < n_) n <<= 1;
		
		{
			size_type two_exp = 0;
			size_type tm = MOD - 1;
			while (tm > 0 && (~tm & 1)) ++two_exp, tm >>= 1;
			assert(1 << two_exp >= n);
		}
		
		std::vector<T> a, b;
		a.reserve(n), b.reserve(n);
		for (size_type i = 0; i < A.size(); ++i) a.emplace_back((static_cast<value_type>(A[i]) % MOD + MOD) % MOD);
		for (size_type i = 0; i < B.size(); ++i) b.emplace_back((static_cast<value_type>(B[i]) % MOD + MOD) % MOD);
		a.resize(n, 0); ntt(a);
		b.resize(n, 0); ntt(b);
		
		const value_type ninv = tk::mod_inv<value_type>(n, MOD);
		for (size_type i = 0; i < n; ++i) a[i] = static_cast<value_type>(a[i]) * static_cast<value_type>(b[i]) % MOD * ninv % MOD;
		b.clear();
		ntt(a, true);
		a.resize(A.size() + B.size() - 1);
		return a;
	}
	
private:
	template<typename T>
	static void ntt(std::vector<T> &A, const bool inv = false) {
		const size_type N = A.size();
		value_type nroot = tk::mod_pow<value_type>(PRIMITIVE_ROOT, (MOD - 1) / N, MOD);
		if (inv) nroot = tk::mod_inv<value_type>(nroot, MOD);
		
		for (size_type n = N; n > 1; n >>= 1) {
			const size_type m = n >> 1;
			std::vector<T> omega;
			omega.reserve(m);
			omega.emplace_back(1);
			for (size_type i = 0; i < m; ++i) omega.emplace_back(static_cast<value_type>(omega.back()) * nroot % MOD);
			value_type half = tk::mod_pow<value_type>(nroot, m, MOD);
			
			for (size_type p = 0; p < N; p += n) {
				for (size_type i = p, ei = p + m; i < ei; ++i) {
					const value_type a = A[i], b = A[i + m];
					A[i] = (a + b) % MOD;
					A[i + m] = (a + b * half % MOD) % MOD * static_cast<value_type>(omega[i - p]) % MOD;
				}
			}
			nroot = nroot * nroot % MOD;
		}
		
		bit_reverse(A);
	}
	
	template<typename T>
	static void bit_reverse(std::vector<T> &A) {
		const size_type N = A.size();
		for (size_type i = 1, j = 0; i < N - 1; ++i) {
			for (size_type k = N >> 1; k > (j ^= k); k >>= 1);
			if (i < j) std::swap(A[i], A[j]);
		}
	}
};

int main() {
	int N, Q;
	cin >> N >> Q;
	vector<int> A(N);
	REP(i, N) scanf("%d", &A[i]);
	vector<int> R(N);
	REP(i, Q) {
		int r;
		scanf("%d", &r);
		++R[r];
	}
	
	reverse(ALL(A));
	auto res = NumberTheoreticTransform<998244353, 3>::multiply(A, R);
	vector<int> B(N);
	REP(i, res.size()) B[(N - 1 - i + N) % N] += res[i];
	REP(i, N) printf("%d%c", B[i], " \n"[i + 1 == N]);
}
0