結果
| 問題 |
No.1307 Rotate and Accumulate
|
| コンテスト | |
| ユーザー |
 kcvlex
|
| 提出日時 | 2020-12-04 23:23:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 109 ms / 5,000 ms |
| コード長 | 17,962 bytes |
| コンパイル時間 | 2,407 ms |
| コンパイル使用メモリ | 177,724 KB |
| 最終ジャッジ日時 | 2025-01-16 16:16:27 |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 19 |
ソースコード
#include <limits>
#include <initializer_list>
#include <utility>
#include <bitset>
#include <tuple>
#include <type_traits>
#include <functional>
#include <string>
#include <array>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iterator>
#include <algorithm>
#include <complex>
#include <random>
#include <numeric>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <regex>
#include <cassert>
#include <cstddef>
#include <variant>
#define endl codeforces
#define ALL(v) std::begin(v), std::end(v)
#define ALLR(v) std::rbegin(v), std::rend(v)
using ll = std::int64_t;
using ull = std::uint64_t;
using pii = std::pair<int, int>;
using tii = std::tuple<int, int, int>;
using pll = std::pair<ll, ll>;
using tll = std::tuple<ll, ll, ll>;
using size_type = ssize_t;
template <typename T> using vec = std::vector<T>;
template <typename T> using vvec = vec<vec<T>>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T, std::size_t Head, std::size_t... Tail>
struct multi_dim_array { using type = std::array<typename multi_dim_array<T, Tail...>::type, Head>; };
template <typename T, std::size_t Head>
struct multi_dim_array<T, Head> { using type = std::array<T, Head>; };
template <typename T, std::size_t... Args> using mdarray = typename multi_dim_array<T, Args...>::type;
template <typename T, typename F, typename... Args>
void fill_seq(T &t, F f, Args... args) {
if constexpr (std::is_invocable<F, Args...>::value) {
t = f(args...);
} else {
for (size_type i = 0; i < t.size(); i++) fill_seq(t[i], f, args..., i);
}
}
template <typename T> vec<T> make_v(size_type sz) { return vec<T>(sz); }
template <typename T, typename... Tail>
auto make_v(size_type hs, Tail&&... ts) {
auto v = std::move(make_v<T>(std::forward<Tail>(ts)...));
return vec<decltype(v)>(hs, v);
}
namespace init__ {
struct InitIO {
InitIO() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
std::cout << std::fixed << std::setprecision(30);
}
} init_io;
}
template <typename T>
T ceil_pow2(T bound) {
T ret = 1;
while (ret < bound) ret *= 2;
return ret;
}
template <typename T>
T ceil_div(T a, T b) { return a / b + !!(a % b); }
namespace math {
template <typename T>
constexpr T mul_id_ele() {
if constexpr (std::is_fundamental<T>::value) {
return T(1);
} else {
return T::mul_id_ele();
}
}
template <typename T>
constexpr T add_id_ele() {
if constexpr (std::is_fundamental<T>::value) {
return T(0);
} else {
return T::add_id_ele();
}
}
template <typename T>
constexpr T pow(const T &n, ll k) {
T ret = mul_id_ele<T>();
T cur = n;
while (k) {
if (k & 1) ret *= cur;
cur *= cur;
k /= 2;
}
return ret;
}
template <typename T>
typename std::enable_if<std::is_integral<T>::value, T>::type
gcd(T a, T b) { return b ? gcd(a % b, b) : a; }
}
namespace math {
template <ull Mod>
struct Modint {
constexpr Modint(ll x) noexcept : x((Mod + x % static_cast<ll>(Mod)) % Mod) { }
constexpr Modint() noexcept : Modint(0) { }
constexpr static Modint add_id_ele() {
return Modint(0);
}
constexpr static Modint mul_id_ele() {
return Modint(1);
}
constexpr ll value() const noexcept {
return static_cast<ll>(x);
}
constexpr Modint& operator+=(const Modint &oth) noexcept {
x += oth.value();
if (Mod <= x) x -= Mod;
return *this;
}
constexpr Modint& operator-=(const Modint &oth) noexcept {
x += Mod - oth.value();
if (Mod <= x) x -= Mod;
return *this;
}
constexpr Modint& operator*=(const Modint &oth) noexcept {
x *= oth.value();
x %= Mod;
return *this;
}
constexpr Modint& operator/=(const Modint &oth) noexcept {
x *= oth.inv().value();
x %= Mod;
return *this;
}
constexpr Modint operator+(const Modint &oth) const noexcept {
return Modint(x) += oth;
}
constexpr Modint operator-(const Modint &oth) const noexcept {
return Modint(x) -= oth;
}
constexpr Modint operator*(const Modint &oth) const noexcept {
return Modint(x) *= oth;
}
constexpr Modint operator/(const Modint &oth) const noexcept {
return Modint(x) /= oth;
}
constexpr Modint operator-() const noexcept {
return Modint((x != 0) * (Mod - x));
}
constexpr bool operator==(const Modint &oth) const noexcept {
return value() == oth.value();
}
template <typename T>
constexpr typename std::enable_if<std::is_integral<T>::value, const Modint&>::type
operator=(T t) noexcept {
(*this) = Modint(std::forward<T>(t));
return *this;
}
constexpr Modint inv() const noexcept {
return ::math::pow(*this, Mod - 2);
}
constexpr ull mod() const noexcept {
return Mod;
}
private:
ull x;
};
template <ull Mod>
Modint<Mod> inv(Modint<Mod> m) {
return m.inv();
}
template <ull Mod>
std::istream& operator>>(std::istream &is, Modint<Mod> &m) {
ll v;
is >> v;
m = v;
return is;
}
template <ull Mod>
std::ostream& operator<<(std::ostream &os, Modint<Mod> m) {
os << m.value();
return os;
}
}
namespace poly {
template <typename T, typename Impl>
struct convolution_interface {
void multiply(vec<T> &a, vec<T> b) {
static_cast<Impl*>(this)->multiply(a, b);
}
// TODO : value_type
template <typename Container>
void multiply_sparse(vec<T> &a, Container terms) {
std::sort(ALLR(terms), [&](const auto &p, const auto &q) { return p.second < q.second; });
a.resize(a.size() + terms[0].second);
for (size_type i = size_type(a.size() - 1); 0 <= i; i--) {
auto cur = std::move(a[i]);
a[i] = T();
for (const auto &[ v, deg ] : terms) if (i + deg < a.size()) a[i + deg] += cur * v;
}
}
// TODO : buggy ?
template <typename Container>
void divide_sparse(vec<T> &a, Container terms) {
std::sort(ALL(terms), [&](const auto &p, const auto &q) { return p.second < q.second; });
assert(terms[0].second == 0);
for (size_type i = 0; i < size_type(a.size()); i++) {
a[i] *= terms[0].first;
for (const auto &[ v, deg ] : terms) if (deg && 0 <= i - deg) a[i] -= v * a[i - deg];
}
}
};
template <typename T>
struct SimpleConvolution : convolution_interface<T, SimpleConvolution<T>> {
void multiply(vec<T> &a, vec<T> b) {
a.resize(a.size() + b.size() - 1);
for (size_type i = size_type(a.size()) - 1; 0 <= i; i--) {
auto cur = std::move(a[i]);
a[i] = T();
for (size_type j = size_type(b.size()); 0 <= j; j--) {
if (i + j < a.size()) a[i + j] += cur * b[j];
}
}
}
};
}
namespace poly {
namespace internal {
template <ull Mod>
constexpr bool is_primitive_root(ll r) {
math::Modint<Mod> mr(r);
for (ll d = 2; d * d <= Mod; d++) {
if ((Mod - 1) % d == 0) {
if (pow(mr, d).value() == 1) return false;
if (pow(mr, (Mod - 1) / d).value() == 1) return false;
}
}
return true;
}
template <ull Mod>
constexpr ll find_primitive_root(ll r) {
return (is_primitive_root<Mod>(r) ? r : find_primitive_root<Mod>(r + 1));
}
template <ull Mod>
constexpr ll find_primitive_root() {
return find_primitive_root<Mod>(2);
}
constexpr auto calc_max_base(ll m) {
ll ret = 0;
for (; m % 2 == 0; ret++, m /= 2);
return ret;
}
}
template <ull Mod, ull PrimitiveRoot = internal::find_primitive_root<Mod>()>
struct NTT : convolution_interface<math::Modint<Mod>, NTT<Mod, PrimitiveRoot>> {
using mint = math::Modint<Mod>;
using value_type = mint;
constexpr NTT()
: root_lis(max_size_log),
iroot_lis(max_size_log)
{
for (size_type i = 0; i < static_cast<size_type>(root_lis.size()); i++) {
root_lis[i] = pow(mint(PrimitiveRoot), (Mod - 1) >> (i + 2)) * -1;
iroot_lis[i] = root_lis[i].inv();
}
}
void multiply(vec<value_type> &a, vec<value_type> b) {
size_type m = a.size(), n = b.size();
size_type sz = 1, res_sz = n + m - 1;
while (sz < res_sz) sz *= 2;
a.resize(sz); b.resize(sz);
ntt(a, sz, false);
ntt(b, sz, false);
auto isz = mint(sz).inv();
for (size_type i = 0; i < sz; i++) a[i] *= b[i] * isz;
ntt(a, sz, true);
a.resize(res_sz);
}
private:
static constexpr size_type max_size_log = internal::calc_max_base(Mod - 1);
static constexpr size_type max_size = 1ll << max_size_log;
static constexpr size_type max_conv_size = max_size * 2;
vec<mint> root_lis, iroot_lis;
using buf_iterator = typename vec<mint>::iterator;
void ntt(vec<value_type> &v, size_type sz, bool inv) {
if (!inv) {
for (int m = sz / 2; m; m /= 2) {
mint mul = 1;
for(int s = 0, k = 0; s < sz; s += 2 * m) {
for(int i = s, j = s + m; i < s + m; ++i, ++j) {
auto x = v[i], y = v[j] * mul;
v[i] = x + y;
v[j] = x - y;
}
mul *= root_lis[__builtin_ctz(++k)];
}
}
} else {
for (int m = 1; m < sz; m *= 2) {
mint mul = 1;
for (int s = 0, k = 0; s < sz; s += 2 * m) {
for (int i = s, j = s + m; i < s + m; i++, j++) {
auto l = v[i], r = v[j];
v[i] = l + r;
v[j] = (l - r) * mul;
}
mul *= iroot_lis[__builtin_ctz(++k)];
}
}
}
}
};
}
namespace poly {
template <typename T, typename ConvolutionImpl>
struct FPS : vec<T> {
using value_type = T;
using vec<T>::vec;
using conv_type = convolution_interface<T, ConvolutionImpl>;
using term_type = std::pair<value_type, size_type>;
static conv_type** get_conv() {
static conv_type *conv = nullptr;
return &conv;
}
static void set_conv(conv_type *conv) {
*(get_conv()) = conv;
}
size_type degree() const {
return size_type(this->size()) - 1;
}
FPS& reverse() {
std::reverse(ALL(*this));
return *this;
}
FPS& extend(size_type deg) {
this->resize(deg + 1);
return *this;
}
FPS& prefix(size_type deg) {
this->resize(deg + 1);
return *this;
}
FPS& shift(size_type s) {
size_type deg = degree();
for (size_type i = 0; i + s <= deg; i++) {
(*this)[i] = (*this)[i + s];
}
return prefix(deg - s);
}
FPS& rshift(size_type s) {
extend(s + degree());
for (size_type i = degree(); 0 <= i; i--) (*this)[i] = (i < s ? 0 : (*this)[i - s]);
return *this;
}
FPS& middle(size_type l, size_type r) {
return this->shift(l).prefix(r - l);
}
FPS& add(const FPS &rhs) {
if (degree() < rhs.degree()) extend(rhs.degree());
for (size_type i = 0; i <= degree(); i++) (*this)[i] += rhs[i];
return *this;
}
FPS& sub(const FPS &rhs) {
if (degree() < rhs.degree()) extend(rhs.degree());
for (size_type i = 0; i <= degree(); i++) (*this)[i] -= rhs[i];
return *this;
}
FPS& mul(FPS rhs) {
if (rhs.degree() < 64) {
auto cmp = rhs.compress();
if (cmp.size()) multiply_sparse(std::move(cmp));
} else {
(*get_conv())->multiply(*this, std::move(rhs));
}
return *this;
}
FPS& mul(T t) {
for (auto &e : (*this)) e *= t;
return *this;
}
FPS& shrink() {
while (1 <= degree() && this->back() == T(0)) this->pop_back();
return *this;
}
// f(0) != 0
FPS& inv(size_type deg) {
FPS orig(*this);
prefix(0);
(*this)[0] = (*this)[0].inv();
for (size_type i = 1; i <= deg; i *= 2) {
FPS d(i * 2);
for (size_type j = 0; j <= std::min(d.degree(), orig.degree()); j++) d[j] = orig[j];
d.mul(*this).mul(*this).prefix(i * 2 - 1);
this->mul(T(2))
.sub(std::move(d))
.prefix(i * 2 - 1);
}
return prefix(deg);
}
// den[0] != 0
FPS& quo(FPS den) {
if (degree() < den.degree()) {
this->clear();
this->push_back(T(0));
return *this;
}
size_type sz = degree() - den.degree();
den.reverse().inv(sz);
return this->reverse()
.prefix(sz)
.mul(std::move(den))
.prefix(sz)
.reverse();
}
// den[0] != 0
FPS& mod(FPS den) {
auto q = *this;
q.quo(den).mul(std::move(den));
return this->sub(std::move(q))
.shrink();
}
FPS& diff() {
for (ll i = 0; i + 1 <= degree() ; i++) (*this)[i] = (*this)[i + 1] * T(i + 1);
if (1 <= degree()) prefix(degree() - 1);
return *this;
}
FPS& integrate() {
this->resize(this->size() + 1);
for (ll i = degree(); 1 <= i; i--) (*this)[i] = (*this)[i - 1] * inv(i);
(*this)[0] = 0;
return *this;
}
value_type operator()(const value_type &x) const noexcept {
value_type ret = 0;
value_type p = 1;
for (auto &&coef : (*this)) {
ret += coef * p;
p *= x;
}
return ret;
}
template <typename Container>
FPS& multiply_sparse(Container terms) {
(*get_conv())->multiply_sparse(*this, terms);
return *this;
}
template <typename Container>
FPS& divide_sparse(Container terms) {
(*get_conv())->divide_sparse(*this, terms);
return *this;
}
vec<term_type> compress() const {
vec<term_type> ret;
for (size_type i = 0; i <= degree(); i++) {
if ((*this)[i] == 0) continue;
ret.emplace_back((*this)[i], i);
}
return ret;
}
};
template <typename Poly> Poly prefix(Poly f, size_type sz) { return f.prefix(sz); }
template <typename Poly> Poly inv(Poly f, size_type sz) { return f.inv(sz); }
template <typename Poly> Poly add(Poly lhs, const Poly &rhs) { return lhs.add(rhs); }
template <typename Poly> Poly sub(Poly lhs, const Poly &rhs) { return lhs.sub(rhs); }
template <typename Poly> Poly mul(Poly lhs, const Poly &rhs) { return lhs.mul(rhs); }
template <typename Poly> Poly quo(Poly lhs, const Poly &rhs) { return lhs.quo(rhs); }
template <typename Poly> Poly mod(Poly lhs, const Poly &rhs) { return lhs.mod(rhs); }
template <typename Poly> Poly mul(Poly lhs, Poly &&rhs) { return lhs.mul(std::move(rhs)); }
template <typename Poly> Poly quo(Poly lhs, Poly &&rhs) { return lhs.quo(std::move(rhs)); }
template <typename Poly> Poly mod(Poly lhs, Poly &&rhs) { return lhs.mod(std::move(rhs)); }
template <typename T, typename ConvImpl>
std::ostream& operator<<(std::ostream &os, const FPS<T, ConvImpl> &f) {
if (f.empty()) return os;
std::cout << f[0];
for (size_type i = 1; i <= f.degree(); i++) os << ' ' << f[i];
return os;
}
template <typename Poly1, typename Poly2>
std::pair<Poly1, Poly1> div(Poly1 lhs, Poly2 &&rhs) {
auto q = std::move(quo(lhs, rhs));
auto m = std::move(mul(q, std::forward<Poly2>(rhs)));
lhs.sub(std::move(m)).shrink();
return std::make_pair(std::move(q), std::move(lhs));
}
// http://q.c.titech.ac.jp/docs/progs/polynomial_division.html
// [x^N](P/Q)
template <typename Poly>
typename Poly::value_type
coef_of_div(Poly P, Poly Q, size_type N) {
assert(Q[0] == 1);
assert(P.size() + 1 == Q.size());
for (; N; N /= 2) {
FPS Qn = Q;
for (size_type i = 1; i < Q.size(); i += 2) Qn[i] *= -1;
auto PQ = std::move(mul(P, Qn));
auto QQ = std::move(mul(Q, Qn));
for (size_type i = 0, offset = N % 2; i < P.size(); i++) P[i] = PQ[2 * i + offset];
for (size_type i = 0; i < Q.size(); i++) Q[i] = QQ[2 * i];
}
return P[0];
}
}
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
constexpr ll mod = 998'244'353;
using mint = math::Modint<mod>;
using fps_t = poly::FPS<mint, poly::NTT<mod>>;
poly::NTT<mod> ntt;
int main() {
fps_t::set_conv(&ntt);
ll n, q;
std::cin >> n >> q;
vec<ll> av(n), rv(q);
for (ll &e : av) std::cin >> e;
for (ll &e : rv) std::cin >> e;
fps_t lhs(n + 1), rhs(n + 1);
vvec<ll> idxv(1e3 + 1);
for (ll i = 0; i < n; i++) lhs[i] += av[i];
for (ll i = 0; i < q; i++) rhs[n - rv[i]] += 1;
lhs.mul(rhs);
vec<ll> ans(n);
for (ll i = 0; i <= lhs.degree(); i++) ans[i % n] += lhs[i].value();
for (ll i = 0; i < n; i++) std::cout << ans[i] << " \n"[i + 1 == n];
return 0;
}