結果
| 問題 | No.1145 Sums of Powers |
| ユーザー |
 QCFium
|
| 提出日時 | 2020-07-31 23:51:48 |
| 言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,096 ms / 2,000 ms |
| コード長 | 11,118 bytes |
| コンパイル時間 | 1,814 ms |
| コンパイル使用メモリ | 185,424 KB |
| 実行使用メモリ | 41,504 KB |
| 最終ジャッジ日時 | 2024-07-06 22:11:50 |
| 合計ジャッジ時間 | 5,692 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,944 KB |
| testcase_02 | AC | 8 ms
6,940 KB |
| testcase_03 | AC | 1,050 ms
41,256 KB |
| testcase_04 | AC | 1,096 ms
41,504 KB |
| testcase_05 | AC | 1,052 ms
41,256 KB |
ソースコード
#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
template<int mod>
struct ModInt{
int x;
ModInt () : x(0) {}
ModInt (int64_t x) : x(x >= 0 ? x % mod : (mod - -x % mod) % mod) {}
ModInt &operator += (const ModInt &p){
if ((x += p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator -= (const ModInt &p) {
if ((x += mod - p.x) >= mod) x -= mod;
return *this;
}
ModInt &operator *= (const ModInt &p) {
x = (int64_t) x * p.x % mod;
return *this;
}
ModInt &operator /= (const ModInt &p) {
*this *= p.inverse();
return *this;
}
ModInt &operator ^= (int64_t p) {
ModInt res = 1;
for (; p; p >>= 1) {
if (p & 1) res *= *this;
*this *= *this;
}
return *this = res;
}
ModInt operator - () const { return ModInt(-x); }
ModInt operator + (const ModInt &p) const { return ModInt(*this) += p; }
ModInt operator - (const ModInt &p) const { return ModInt(*this) -= p; }
ModInt operator * (const ModInt &p) const { return ModInt(*this) *= p; }
ModInt operator / (const ModInt &p) const { return ModInt(*this) /= p; }
ModInt operator ^ (int64_t p) const { return ModInt(*this) ^= p; }
bool operator == (const ModInt &p) const { return x == p.x; }
bool operator != (const ModInt &p) const { return x != p.x; }
explicit operator int() const { return x; }
ModInt &operator = (const int p) { x = p; return *this;}
ModInt inverse() const {
int a = x, b = mod, u = 1, v = 0, t;
while (b > 0) {
t = a / b;
a -= t * b;
std::swap(a, b);
u -= t * v;
std::swap(u, v);
}
return ModInt(u);
}
friend std::ostream & operator << (std::ostream &stream, const ModInt<mod> &p) {
return stream << p.x;
}
friend std::istream & operator >> (std::istream &stream, ModInt<mod> &a) {
int64_t x;
stream >> x;
a = ModInt<mod>(x);
return stream;
}
};
template<int mod> struct MComb {
using mint = ModInt<mod>;
std::vector<mint> fact;
std::vector<mint> inv;
MComb (int n) { // O(n + log(mod))
fact = std::vector<mint>(n + 1, 1);
for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * mint(i);
inv.resize(n + 1);
inv[n] = fact[n] ^ (mod - 2);
for (int i = n; i--; ) inv[i] = inv[i + 1] * mint(i + 1);
}
mint ncr(int n, int r) {
return fact[n] * inv[r] * inv[n - r];
}
mint npr(int n, int r) {
return fact[n] * inv[n - r];
}
mint nhr(int n, int r) {
assert(n + r - 1 < (int) fact.size());
return ncr(n + r - 1, r);
}
};
// only with NTT-friendly mods
template<int mod> struct NTT { // mint version
using mint = ModInt<mod>;
int get_mod() { return mod; }
static constexpr std::pair<int, int> proot_map[] = {
{469762049, 3}, // 2^26
{998244353, 3}, // 2^23
{897581057, 3},
{645922817, 3},
{880803841, 26},
{1004535809, 3}, // 2^21
{1012924417, 5}
};
static constexpr int proot_map_size = sizeof(proot_map) / sizeof(*proot_map);
static constexpr int get_proot(int index = 0) {
return index == proot_map_size ? throw 0 :
proot_map[index].first == mod ? proot_map[index].second : get_proot(index + 1);
}
static constexpr int proot = get_proot();
void ntt(std::vector<mint> &a, bool inverse) const {
int n = a.size();
assert((n & -n) == n);
mint h = mint(proot) ^ ((mod - 1) / n);
if (inverse) h = h.inverse();
for (int i = 0, j = 1; j < n - 1; j++) {
for (int k = n >> 1; k > (i ^= k); k >>= 1);
if (j < i) std::swap(a[i], a[j]);
}
for (int i = 1; i < n; i <<= 1) {
mint base = h ^ (n / i / 2);
mint w = 1;
std::vector<mint> ws(i);
for (int j = 0; j < i; j++) ws[j] = w, w *= base;
for (int j = 0; j < n; j += i << 1) {
for (int k = 0; k < i; k++) {
mint u = a[k + j];
mint d = a[k + j + i] * ws[k];
a[k + j] = u + d;
a[k + j + i] = u - d;
}
}
}
if (inverse) {
mint ninv = mint(a.size()).inverse();
for (auto &i : a) i *= ninv;
}
}
std::vector<mint> convolve_self(std::vector<mint> a) const {
if (!a.size()) return {};
size_t n_ = a.size();
size_t size = 1;
for (; size < n_ + n_; size <<= 1);
a.resize(size);
ntt(a, false);
for (auto &i : a) i *= i;
ntt(a, true);
a.resize(n_ + n_ - 1);
return a;
}
std::vector<mint> convolve(const std::vector<mint> &a_, const std::vector<mint> &b_) const {
if (!a_.size() || !b_.size()) return {};
if (&a_ == &b_) return convolve_self(a_);
std::vector<mint> a = a_, b = b_;
size_t size = 1;
for (; size < a_.size() + b_.size(); size <<= 1);
a.resize(size);
b.resize(size);
ntt(a, false);
ntt(b, false);
for (size_t i = 0; i < size; i++) a[i] *= b[i];
ntt(a, true);
a.resize(a_.size() + b_.size() - 1);
return a;
}
};
template<int mod> struct Polynomial {
using mint = ModInt<mod>;
static NTT<mod> ntt;
std::vector<mint> data;
Polynomial () = default;
Polynomial (const std::vector<mint> &data) : data(data) {}
template<typename T> Polynomial (const std::vector<T> &data) : data(data.begin(), data.end()) {}
template<typename T> Polynomial (std::initializer_list<T> c) : data(c.begin(), c.end()) {}
void normalize() {
while (data.size() && !data.back().x) data.pop_back();
}
Polynomial & operator += (const Polynomial &rhs) {
data.resize(std::max(data.size(), rhs.data.size()));
for (size_t i = 0; i < rhs.size(); i++) data[i] += rhs[i];
return *this;
}
Polynomial & operator -= (const Polynomial &rhs) {
data.resize(std::max(data.size(), rhs.data.size()));
for (size_t i = 0; i < rhs.size(); i++) data[i] -= rhs[i];
return *this;
}
Polynomial & operator *= (const Polynomial &rhs) {
data = ntt.convolve(data, rhs.data);
return *this;
}
Polynomial & operator /= (Polynomial rhs) {
normalize();
rhs.normalize();
if (data.size() < rhs.data.size()) data = { 0 };
else {
int size = data.size() - rhs.data.size() + 1;
std::reverse(data.begin(), data.end());
std::reverse(rhs.data.begin(), rhs.data.end());
data.resize(size);
rhs.data.resize(size);
rhs = rhs.inverse();
data = ntt.convolve(data, rhs.data);
data.resize(size);
std::reverse(data.begin(), data.end());
}
return *this;
}
Polynomial & operator %= (const Polynomial &rhs) {
*this -= *this / rhs * rhs;
normalize();
return *this;
}
Polynomial & operator <<= (mint c) {
if (!data.size()) return *this;
int n = data.size();
MComb<mod> com(n - 1);
std::vector<mint> r0 = com.fact;
for (int i = 0; i < n; i++) r0[i] *= data[i];
std::vector<mint> r1 = com.inv;
mint cur = 1;
for (int i = 0; i < n; i++) r1[i] *= cur, cur *= c;
std::reverse(r1.begin(), r1.end());
data = ntt.convolve(r0, r1);
data.erase(data.begin(), data.begin() + n - 1);
for (int i = 0; i < n; i++) data[i] *= com.inv[i];
return *this;
}
Polynomial &diff() {
if (!data.size()) return *this;
for (size_t i = 1; i < data.size(); i++) data[i - 1] = data[i] * i;
data.pop_back();
return *this;
}
Polynomial &integrate() {
if (!data.size()) return *this;
data.push_back(0);
for (size_t i = data.size(); --i; ) data[i] = data[i - 1] / i;
data[0] = 0;
return *this;
}
/* TODO : understand those ! */
Polynomial &logize() {
int n = data.size();
if (!n) return *this; // should not happen
*this = (inverse() * diffed()).integrated();
data.resize(n);
return *this;
}
Polynomial &expize() {
int n = data.size();
Polynomial res{1};
data[0] += 1;
for (int i = 1; i < n; i <<= 1) {
Polynomial r0(std::vector<mint>(data.begin(), data.begin() + std::min<size_t>(data.size(), i << 1)));
Polynomial r1 = res;
r1.data.resize(i << 1);
res *= r0 - r1.log();
res.data.resize(i << 1);
}
res.data.resize(n);
return *this = res;
}
Polynomial operator + (const Polynomial &rhs) const { return Polynomial(*this) += rhs; }
Polynomial operator - (const Polynomial &rhs) const { return Polynomial(*this) -= rhs; }
Polynomial operator * (const Polynomial &rhs) const { return Polynomial(*this) *= rhs; }
Polynomial operator / (const Polynomial &rhs) const { return Polynomial(*this) /= rhs; }
Polynomial operator % (const Polynomial &rhs) const { return Polynomial(*this) %= rhs; }
Polynomial operator << (mint c) const { return Polynomial(*this) <<= c; }
Polynomial exp() const { return Polynomial(*this).expize(); }
Polynomial log() const { return Polynomial(*this).logize(); }
Polynomial diffed() const { return Polynomial(*this).diff(); }
Polynomial integrated() const { return Polynomial(*this).integrate(); }
Polynomial inverse () const {
assert(data.size() && data[0].x);
std::vector<mint> res{data[0].inverse()};
for (size_t i = 1; i < data.size(); i <<= 1) {
auto next_res = res;
next_res.resize(i << 2);
ntt.ntt(next_res, false);
std::vector<mint> h(data.begin(), data.begin() + std::min<size_t>(data.size(), i + i));
h.resize(i << 2);
ntt.ntt(h, false);
for (size_t j = 0; j < i << 2; j++) next_res[j] *= next_res[j], next_res[j] *= h[j];
ntt.ntt(next_res, true);
next_res.resize(i << 1);
for (auto &i : next_res) i = -i;
for (size_t j = 0; j < i; j++) next_res[j] += res[j] + res[j];
swap(res, next_res);
}
res.resize(data.size());
return Polynomial(res);
}
static std::vector<Polynomial> interplate0_tree(const std::vector<mint> &list) {
int n_ = list.size();
int n = 1;
for (; n < n_; n <<= 1);
std::vector<Polynomial> tree(n << 1, Polynomial({1}));
for (int i = 0; i < n_; i++) tree[i + n] = Polynomial({-list[i], 1});
for (int i = n; --i; ) tree[i] = tree[i << 1] * tree[i << 1 | 1];
return tree;
}
std::vector<mint> eval(const std::vector<mint> &list) const {
int q_ = list.size();
auto tree = interplate0_tree(list);
int q = tree.size() >> 1;
std::vector<Polynomial> res_tree(q << 1);
res_tree[1] = *this;
for (int i = 1; i < q; i++) {
res_tree[i << 1] = tree[i << 1].size() ? res_tree[i] % tree[i << 1] : res_tree[i];
res_tree[i << 1 | 1] = tree[i << 1 | 1].size() ? res_tree[i] % tree[i << 1 | 1] : res_tree[i];
}
std::vector<mint> res(q_);
for (int i = 0; i < q_; i++) res[i] = res_tree[i + q][0];
return res;
}
mint & operator [] (int i) { return data[i]; }
const mint & operator [] (int i) const { return data[i]; }
std::string to_string() const {
std::string res = "";
for (int i = 0; i < (int) data.size(); i++) {
if (i) res += " ";
res += std::to_string(data[i].x);
}
return res;
}
size_t size() const { return data.size(); }
};
template<int mod> NTT<mod> Polynomial<mod>::ntt;
typedef Polynomial<998244353> Poly;
typedef ModInt<998244353> mint;
int main() {
int n = ri();
int m = ri();
int a[n];
for (auto &i : a) i = ri();
int n2 = n;
for (; n2 < n; n2 <<= 1);
Poly prod[n2 << 1];
Poly exc_prod[n2 << 1];
for (int i = 0; i < n2; i++) {
if (i < n) prod[i + n2] = {1, -a[i]};
else prod[i + n2] = { 1 };
exc_prod[i + n2] = { 1 };
}
for (int i = n2; --i; ) {
prod[i] = prod[i << 1] * prod[i << 1 | 1];
exc_prod[i] = exc_prod[i << 1] * prod[i << 1 | 1] + exc_prod[i << 1 | 1] * prod[i << 1];
}
prod[1].data.resize(m + 1);
Poly r0 = exc_prod[1] * prod[1].inverse();
r0.data.resize(m + 1);
r0.data.erase(r0.data.begin());
printf("%s\n", r0.to_string().c_str());
return 0;
}