結果
問題 | No.1307 Rotate and Accumulate |
ユーザー |
![]() |
提出日時 | 2020-12-30 12:45:21 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 100 ms / 5,000 ms |
コード長 | 4,951 bytes |
コンパイル時間 | 2,152 ms |
コンパイル使用メモリ | 201,432 KB |
最終ジャッジ日時 | 2025-01-17 08:29:50 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 19 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:182:24: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 182 | REP(i, N) scanf("%d", &A[i]); | ~~~~~^~~~~~~~~~~~~ main.cpp:186:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 186 | scanf("%d", &r); | ~~~~~^~~~~~~~~~
ソースコード
#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]);}