結果
| 問題 | No.3414 Aperiodic Sequence |
| コンテスト | |
| ユーザー |
 t98slider
|
| 提出日時 | 2025-12-21 00:50:11 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 175 ms / 3,000 ms |
| コード長 | 6,856 bytes |
| 記録 | |
| コンパイル時間 | 6,608 ms |
| コンパイル使用メモリ | 334,448 KB |
| 実行使用メモリ | 17,300 KB |
| 最終ジャッジ日時 | 2025-12-21 00:50:20 |
| 合計ジャッジ時間 | 9,373 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 15 |
ソースコード
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;
template <class mint> struct Polynomial : std::vector<mint> {
using std::vector<mint>::vector;
using poly = Polynomial;
poly& operator=(const std::vector<mint>& rhs) {
this->assign(rhs.begin(), rhs.end());
return *this;
}
poly& operator+=(const poly& rhs) {
int rn = rhs.size();
if(this->size() < rn) this->resize(rn);
for(int i = 0; i < rn; i++) (*this)[i] += rhs[i];
return *this;
}
poly& operator-=(const poly& rhs) {
int rn = rhs.size();
if(this->size() < rn) this->resize(rn);
for(int i = 0; i < rn; i++) (*this)[i] -= rhs[i];
return *this;
}
poly& operator*=(const poly& rhs) {
return *this = atcoder::convolution(*this, rhs);
}
poly inv() const {
const int n = this->size();
poly res;
res.reserve(n);
res.emplace_back((*this)[0].inv());
while(res.size() < n){
const int m = 2 * res.size();
std::vector<mint> buf(m), fres(m);
std::copy(this->begin(), this->begin() + std::min(m, n), buf.begin());
std::copy(res.begin(), res.end(), fres.begin());
atcoder::internal::butterfly(buf);
atcoder::internal::butterfly(fres);
for (int i = 0; i < m; i++) buf[i] *= fres[i];
atcoder::internal::butterfly_inv(buf);
std::fill(buf.begin(), buf.begin() + res.size(), mint::raw(0));
atcoder::internal::butterfly(buf);
for (int i = 0; i < m; i++) buf[i] *= fres[i];
atcoder::internal::butterfly_inv(buf);
mint coef = -(mint::raw(m) * mint::raw(m)).inv();
for (int i = res.size(); i < std::min(m, n); i++) res.emplace_back(buf[i] * coef);
}
return res;
}
poly operator+() const { return *this; }
poly operator-() const { return poly() - *this; }
friend poly operator+(const poly& lhs, const poly& rhs) {
return poly(lhs) += rhs;
}
friend poly operator-(const poly& lhs, const poly& rhs) {
return poly(lhs) -= rhs;
}
friend poly operator*(const poly& lhs, const poly& rhs) {
return poly(lhs) *= rhs;
}
poly deriv() const {
const int deg = this->size();
poly res(std::max(0, deg - 1));
mint coef = 1;
for(int i = 1; i < deg; i++) {
res[i - 1] = (*this)[i] * coef;
coef++;
}
return res;
}
poly integ() const {
const int deg = this->size();
poly res(deg + 1);
res[0] = 0;
if (deg > 0) res[1] = 1;
auto mod = mint::mod();
for (int i = 2; i <= deg; i++) res[i] = (-res[mod % i]) * (mod / i);
for (int i = 0; i < deg; i++) res[i + 1] *= (*this)[i];
return res;
}
poly log() const {
return (this->deriv() * this->inv()).integ();
}
poly exp() const {
const int deg = this->size();
// 1/iのテーブルの作成
int r = 2 << std::__lg(deg);
auto mod = mint::mod();
vector<mint> iv(r + 1);
iv[1] = 1;
for (int i = 2; i <= r; i++) iv[i] = (-iv[mod % i]) * (mod / i);
auto internal_butterfly_inv = [&](poly& f){
atcoder::internal::butterfly_inv(f);
mint iz = mint::raw(f.size()).inv();
for (auto &&v : f) v *= iz;
};
poly res = {1, this->size() >= 2 ? (*this)[1] : 0};
poly c{1}, z1, z2{1, 1};
for (int m = 2; m < deg; m *= 2){
auto y = res;
y.resize(2 * m);
atcoder::internal::butterfly(y);
z1 = z2;
poly z(m);
for (int i = 0; i < m; i++) z[i] = y[i] * z1[i];
internal_butterfly_inv(z);
std::fill(z.begin(), z.begin() + (m / 2), mint::raw(0));
atcoder::internal::butterfly(z);
for (int i = 0; i < m; ++i) z[i] *= -z1[i];
internal_butterfly_inv(z);
c.insert(c.end(), z.begin() + (m / 2), z.end());
z2 = c;
z2.resize(2 * m);
atcoder::internal::butterfly(z2);
poly x(m);
std::copy(this->begin(), this->begin() + std::min(m, deg), x.begin());
for(int i = 0; i < m; i++) x[i] = x[i + 1] * mint::raw(i + 1);
x.back() = 0;
atcoder::internal::butterfly(x);
for (int i = 0; i < m; ++i) x[i] *= y[i];
internal_butterfly_inv(x);
x -= res.deriv();
x.resize(2 * m);
for (int i = 0; i < m - 1; ++i) x[m + i] = x[i], x[i] = mint::raw(0);
atcoder::internal::butterfly(x);
for (int i = 0; i < 2 * m; ++i) x[i] *= z2[i];
internal_butterfly_inv(x);
for(int i = x.size() - 1; i >= 1; i--) x[i] = iv[i] * x[i - 1];
x[0] = 0;
for (int i = m; i < min(deg, 2 * m); ++i) x[i] += (*this)[i];
std::fill(x.begin(), x.begin() + m, mint::raw(0));
atcoder::internal::butterfly(x);
for (int i = 0; i < 2 * m; ++i) x[i] *= y[i];
internal_butterfly_inv(x);
res.insert(res.end(), x.begin() + m, x.end());
}
return res;
}
friend std::ostream& operator << (std::ostream &os, const poly vec) noexcept {
if (vec.empty()) return os;
os << vec[0].val();
for (auto it = vec.begin(); ++it != vec.end(); ) os << ' ' << it->val();
return os;
}
};
using poly = Polynomial<mint>;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, v;
cin >> n >> m;
vector<poly> tb(n);
for(int i = 0; i < n; i++){
cin >> v;
tb[i] = vector<mint>({1, -v});
}
auto prod = [&](auto prod, int l, int r) -> void {
if(r <= l + 1) return;
int mid = (l + r) / 2;
prod(prod, l, mid);
prod(prod, mid, r);
tb[l] *= tb[mid];
};
prod(prod, 0, n);
if(tb[0].size() < m + 1) tb[0].resize(m + 1);
auto P = tb[0].deriv() * tb[0].inv();
P *= {0, -1};
vector<int> mu(m + 1, -1);
vector<bool> used(m + 1);
for(int i = 2; i <= m; i++){
if(used[i]) continue;
for(int j = i; j <= m; j += i){
mu[j] = -mu[j];
used[j] = true;
}
}
for(int i = 2; i * i <= m; i++){
int d = i * i;
for(int j = d; j <= m; j += d) mu[j] = 0;
}
poly ans(m);
for(int i = 1; i <= m; i++){
if(mu[i] == 0) continue;
mint vl = mint::raw(1);
for(int j = i; j <= m; j += i){
vl *= P[i];
ans[j - 1] += mu[i] == -1 ? vl : -vl;
}
}
cout << ans << '\n';
}