結果
| 問題 | No.3447 Power Projection(constant) |
| コンテスト | |
| ユーザー |
 Naru820
|
| 提出日時 | 2026-02-20 21:40:37 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 17,014 bytes |
| 記録 | |
| コンパイル時間 | 8,582 ms |
| コンパイル使用メモリ | 410,224 KB |
| 実行使用メモリ | 7,976 KB |
| 最終ジャッジ日時 | 2026-02-20 21:40:48 |
| 合計ジャッジ時間 | 10,306 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 22 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
#define fast std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr)
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = atcoder::modint998244353;
constexpr ll inf = 2e18;
constexpr ll mod = 998244353;
static void judge(bool c) {
std::cout << (c ? "Yes" : "No") << '\n';
}
static vector<mint> trim(vector<mint>& a){ while(!a.empty() && a.back()==mint(0)) a.pop_back(); return a; }
vector<mint> operator*(const vector<mint>& a,const vector<mint>& b){
if(a.empty()||b.empty()) return {};
auto c = convolution(a,b);
return c;
}
vector<mint> prod(const vector<mint> &f,const vector<mint> &g){ return f*g; }
static vector<mint> mul_trunc(const vector<mint>& a,const vector<mint>& b,int n){
if(a.empty()||b.empty()) return vector<mint>();
int need = min<int>(n+1,(int)a.size()+(int)b.size()-1);
auto c=convolution(a,b);
c.resize(need);
return c;
}
static vector<mint> poly_inv(const vector<mint>& a,int n){
if(a.empty() || a[0]==mint(0)) throw runtime_error("poly_inv: bad input");
vector<mint> r(1, a[0].inv());
int m = 1;
vector<mint> two_minus_t,as;
while(m <= n){
int cur = m<<1;
as.assign(min((int)a.size(), cur),mint(0));
for(int i=0;i<(int)as.size();++i) as[i]=a[i];
auto t = mul_trunc(r, as, cur-1);
two_minus_t.assign(cur, mint(0));
two_minus_t[0] = mint(2) - (t.size()>0? t[0] : mint(0));
for(int i=1;i<cur;i++){
mint ti = (i < (int)t.size() ? t[i] : mint(0));
two_minus_t[i] = -ti;
}
r = mul_trunc(r, two_minus_t, cur-1);
r.resize(cur);
m = cur;
}
r.resize(n+1);
return r;
}
vector<mint> div(const vector<mint> &f,const vector<mint> &g,int n){
if(g.empty()) throw runtime_error("div: g is zero");
if(g[0]==mint(0)) throw runtime_error("div: g[0]==0");
int need = n+1;
vector<mint> ig = poly_inv(g, n);
auto res = mul_trunc(f, ig, n);
res.resize(need);
return res;
}
static vector<mint> derivative(const vector<mint>& a){
if(a.size()<=1) return vector<mint>();
vector<mint> r(a.size()-1);
for(size_t i=1;i<a.size();++i) r[i-1]=a[i]*mint((ll)i);
return r;
}
static vector<mint> integral(const vector<mint>& a){
vector<mint> r(a.size()+1);
r[0]=mint(0);
for(size_t i=0;i<a.size();++i) r[i+1]=a[i]/mint((ll)(i+1));
return r;
}
vector<mint> log(const vector<mint> &f,int n){
if(f.empty()||f[0]!=mint(1)) throw runtime_error("log: constant term must be 1");
auto df = derivative(f);
auto invf = poly_inv(f, n);
auto mul = mul_trunc(df, invf, max(0,n-1));
auto res = ::integral(mul);
res.resize(n+1);
return res;
}
vector<mint> exp(const vector<mint> &f,int n){
if(f.empty()||f[0]!=mint(0)) throw runtime_error("exp: constant term must be 0");
vector<mint> g(1,mint(1));
int m=1;
while(m<=n){
int cur = m<<1;
int need = min(cur, n+1);
vector<mint> ln = log(g, need-1);
vector<mint> diff(need);
for(int i=0;i<need;i++){
mint fi = (i < (int)f.size() ? f[i] : mint(0));
mint lni = (i < (int)ln.size() ? ln[i] : mint(0));
diff[i] = fi - lni;
}
diff[0] = diff[0] + mint(1);
g = mul_trunc(g, diff, need-1);
g.resize(need);
m = cur;
}
g.resize(n+1);
return g;
}
vector<mint> composition(const vector<mint> &f,const vector<mint> &g,int n){
if(g.empty() || g[0]!=mint(0)) throw runtime_error("composition: g[0] must be 0");
int degf = (int)f.size();
vector<mint> res(1,mint(0));
for(int i=degf-1;i>=0;--i){
res = mul_trunc(res, g, n);
if((int)res.size()>n+1) res.resize(n+1);
if((int)res.size()<n+1) res.resize(n+1,mint(0));
res[0] += f[i];
}
res.resize(n+1);
return res;
}
vector<mint> inv(const vector<mint> &f,int n){
if(f.empty()) throw runtime_error("inv composition: empty");
if(f[0]!=mint(0)) throw runtime_error("inv composition: constant term must be 0");
if(f.size()<=1 || f[1]==mint(0)) throw runtime_error("inv composition: linear coeff must be nonzero");
vector<mint> g(1,mint(0));
int m=1;
while(m<=n){
int cur = m<<1;
int need = min(cur, n+1);
auto fg = composition(f, g, need-1);
vector<mint> delta(need);
for(int i=0;i<need;i++){
mint val = (i==1? mint(1) : mint(0));
mint fgc = (i < (int)fg.size() ? fg[i] : mint(0));
delta[i] = fgc - val;
}
auto fprime = derivative(f);
auto fprimg = composition(fprime, g, need-1);
auto invfprimg = poly_inv(fprimg, need-1);
auto correction = mul_trunc(delta, invfprimg, need-1);
g.resize(need);
for(int i=0;i<need;i++){
mint gi = (i < (int)g.size() ? g[i] : mint(0));
mint corr = (i < (int)correction.size() ? correction[i] : mint(0));
g[i] = gi - corr;
}
m = cur;
}
g.resize(n+1);
return g;
}
static size_t ceil2(size_t n){
size_t p = 1;
while(p < n) p <<= 1;
return p;
}
static vector<mint> poly_mod(vector<mint> f, vector<mint> g){
f = trim(f);
g = trim(g);
if(g.empty()) throw runtime_error("poly_mod: g empty");
if(f.size() < g.size()) return f;
int n = (int)f.size() - 1;
int m = (int)g.size() - 1;
int qdeg = n - m;
vector<mint> f_rev = f;
reverse(all(f_rev));
vector<mint> g_rev = g;
reverse(all(g_rev));
int need = qdeg + 1;
f_rev.resize(need);
g_rev.resize(need);
auto inv_g_rev = poly_inv(g_rev, qdeg);
auto q_rev = mul_trunc(f_rev, inv_g_rev, qdeg);
q_rev.resize(need);
vector<mint> q = q_rev;
reverse(all(q));
q = trim(q);
auto qg = prod(q, g);
int rem_size = (int)g.size() - 1;
if (rem_size < 0) rem_size = 0;
vector<mint> r(rem_size);
for(int i = 0; i < rem_size; i++) {
mint fi = (i < (int)f.size() ? f[i] : mint(0));
mint qgi = (i < (int)qg.size() ? qg[i] : mint(0));
r[i] = fi - qgi;
}
return trim(r);
}
vector<mint> multipoint_eval(const vector<mint> &a, const vector<int> &point){
size_t m = point.size();
if(m == 0) return vector<mint>();
size_t m2 = ceil2(m);
vector<vector<mint>> g(m2 + m2, vector<mint>(1, mint(1)));
for(size_t i=0;i<m;i++){
mint xi = mint((long long)point[i]);
g[m2 + i] = vector<mint>{-xi, mint(1)};
}
for(size_t i = m2; i-- > 1; ){
g[i] = prod(g[i<<1], g[i<<1|1]);
}
g[1] = poly_mod(a, g[1]);
for(size_t i = 2; i < m2 + m; ++i){
g[i] = poly_mod(g[i>>1], g[i]);
}
vector<mint> ys(m);
for(size_t i=0;i<m;i++){
ys[i] = (g[m2 + i].empty() ? mint(0) : g[m2 + i][0]);
}
return ys;
}
class BinomialCoefficient {
private:
long long mod;
std::vector<long long> fact;
std::vector<long long> inv_fact;
long long power(long long base, long long exp) {
long long res = 1;
base %= mod;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % mod;
base = (base * base) % mod;
exp /= 2;
}
return res;
}
public:
BinomialCoefficient(int n_max, long long m) : mod(m) {
fact.resize(n_max + 1);
inv_fact.resize(n_max + 1);
fact[0] = 1;
inv_fact[0] = 1;
for (int i = 1; i <= n_max; ++i) {
fact[i] = (fact[i - 1] * i) % mod;
}
inv_fact[n_max] = power(fact[n_max], mod - 2);
for (int i = n_max; i > 0; --i) {
inv_fact[i - 1] = (inv_fact[i] * i) % mod;
}
}
long long com(int n, int r) {
if (r < 0 || n < r) {
return 0;
}
if (static_cast<size_t>(n) >= fact.size()) {
return -1;
}
long long result = fact[n];
result = (result * inv_fact[r]) % mod;
result = (result * inv_fact[n - r]) % mod;
return result;
}
};
vector<mint> power(const vector<mint> &f, long long e, int n) {
if (f.empty()) return vector<mint>(n + 1, 0);
if (e == 0) {
vector<mint> res(n + 1, 0);
res[0] = 1;
return res;
}
int shift = 0;
while (shift < (int)f.size() && f[shift] == mint(0)) shift++;
if (shift == (int)f.size()) return vector<mint>(n + 1, 0);
if (e > 0 && shift > (n / e)) return vector<mint>(n + 1, 0);
vector<mint> g;
g.reserve(f.size() - shift);
for (int i = shift; i < (int)f.size(); ++i) g.push_back(f[i]);
mint c = g[0];
mint inv_c = c.inv();
for (auto& x : g) x *= inv_c;
auto logg = log(g, n);
for (auto& x : logg) x *= mint(e);
auto expg = exp(logg, n);
mint c_pow = c.pow(e);
for (auto& x : expg) x *= c_pow;
vector<mint> res(n + 1, 0);
int total_shift = (int)(e * shift);
for (int i = 0; i < (int)expg.size(); ++i) {
if (total_shift + i <= n) res[total_shift + i] = expg[i];
}
return res;
}
vector<mint> get_power_sums(const vector<ll>& arr, int k_max) {
int n = arr.size();
if (n == 0) {
return vector<mint>(k_max + 1, 0);
}
function<vector<mint>(int, int)> dc_prod =
[&](int l, int r) -> vector<mint> {
if (l == r) {
return {1, -mint(arr[l])};
}
int mid = (l + r) / 2;
auto left = dc_prod(l, mid);
auto right = dc_prod(mid + 1, r);
return prod(left, right);
};
vector<mint> Q = dc_prod(0, n - 1);
vector<mint> dQ = derivative(Q);
vector<mint> invQ = poly_inv(Q, k_max);
vector<mint> R = mul_trunc(dQ, invQ, k_max);
R.resize(k_max + 1, 0);
vector<mint> P_sum(k_max + 1);
P_sum[0] = n;
for (int i = 1; i <= k_max; ++i) {
P_sum[i] = -R[i - 1];
}
return P_sum;
}
mint bostan_mori(vector<mint> f, vector<mint> g, ll n) {
f = trim(f);
g = trim(g);
if (g.empty() || g[0] == mint(0)) throw runtime_error("bostan_mori: bad denominator");
while (n > 0) {
auto g_neg = g;
for (size_t i = 1; i < g_neg.size(); i += 2) g_neg[i] = -g_neg[i];
auto g_sq = convolution(g, g_neg);
auto f_gneg = convolution(f, g_neg);
size_t g_sz = (g_sq.size() + 1) >> 1;
g.resize(g_sz);
for (size_t i = 0; i < g_sz; ++i) {
g[i] = (2 * i < g_sq.size() ? g_sq[2 * i] : mint(0));
}
size_t f_sz = (f_gneg.size() + (n & 1) + 1) >> 1;
f.resize(f_sz);
int parity = (n & 1);
for (size_t i = 0; i < f_sz; ++i) {
size_t idx = 2 * i + parity;
f[i] = (idx < f_gneg.size() ? f_gneg[idx] : mint(0));
}
n >>= 1;
}
return f.empty() ? mint(0) : f[0] * g[0].inv();
}
namespace fps_internal {
vector<vector<mint>> precompute_powers(const vector<mint>& g, int n, int k) {
vector<vector<mint>> powers;
powers.reserve(32);
powers.push_back(g);
int deg = 1;
while (deg < k) {
auto next_g = mul_trunc(powers.back(), powers.back(), n);
powers.push_back(next_g);
deg <<= 1;
}
return powers;
}
vector<mint> compose_dc(const vector<mint>& f, int l, int r,
const vector<vector<mint>>& g_powers, int level, int n) {
if (l + 1 == r) {
if (l < (int)f.size()) return {f[l]};
return {mint(0)};
}
int mid = (l + r) >> 1;
auto h_left = compose_dc(f, l, mid, g_powers, level - 1, n);
auto h_right = compose_dc(f, mid, r, g_powers, level - 1, n);
auto rhs = mul_trunc(h_right, g_powers[level - 1], n);
if (h_left.size() < rhs.size()) h_left.resize(rhs.size(), mint(0));
for (size_t i = 0; i < rhs.size(); ++i) h_left[i] += rhs[i];
return h_left;
}
}
vector<mint> compose(const vector<mint>& f, const vector<mint>& g, int n) {
if (f.empty()) return {};
if (g.empty()) return {f[0]};
int deg_f = (int)f.size() - 1;
if (deg_f == 0) return {f[0]};
int k = 1;
int level = 0;
while (k <= deg_f) {
k <<= 1;
level++;
}
auto g_powers = fps_internal::precompute_powers(g, n, k);
return fps_internal::compose_dc(f, 0, k, g_powers, level, n);
}
vector<mint> inverse(const vector<mint>& f, int n) {
if (f.empty() || f[0] != mint(0)) throw runtime_error("inverse: constant term must be 0");
if (f.size() <= 1 || f[1] == mint(0)) throw runtime_error("inverse: linear coeff must be nonzero");
vector<mint> g = {mint(0)};
g = {mint(0), f[1].inv()};
int m = 1;
while (m <= n) {
int cur = m << 1;
int need = min(cur, n + 1);
auto fg = compose(f, g, need - 1);
if (fg.size() > 1) fg[1] -= mint(1);
auto f_prime = derivative(f);
auto fpg = compose(f_prime, g, need - 1);
auto inv_fpg = poly_inv(fpg, need - 1);
auto correction = mul_trunc(fg, inv_fpg, need - 1);
g.resize(need);
for (int i = 0; i < need; ++i) {
if (i < (int)correction.size()) g[i] -= correction[i];
}
m = cur;
}
g.resize(n + 1);
return g;
}
vector<mint> power_projection(const vector<mint>& f, const vector<mint>& g) {
using fps = vector<mint>;
int n = (int)f.size() - 1;
if (n < 0) return {};
auto pack = [](const vector<fps>& V, int n_x, int width) -> fps {
int size = n_x * width;
if (V.empty()) return {};
int real_size = (int)V.size() * width + (int)V.back().size();
fps res(real_size, mint(0));
for (int i = 0; i < (int)V.size(); ++i) {
for (int j = 0; j < (int)V[i].size(); ++j) {
res[i * width + j] = V[i][j];
}
}
return res;
};
auto unpack = [](const fps& flat, int n_x, int width, int deg_y_limit) -> vector<fps> {
vector<fps> res(n_x);
for (int i = 0; i < n_x; ++i) {
int start = i * width;
int end = min((int)flat.size(), start + width);
if (start >= (int)flat.size()) continue;
int len = min(end - start, deg_y_limit + 1);
res[i].resize(len);
for (int j = 0; j < len; ++j) {
res[i][j] = flat[start + j];
}
}
return res;
};
int k = 1;
vector<fps> P(n + 1, fps(1));
vector<fps> Q(n + 1, fps(2));
for (int i = 0; i <= n; ++i) P[i][0] = (i < (int)g.size() ? g[i] : mint(0));
Q[0][0] = 1;
for (int i = 1; i <= n; ++i) {
if (i < (int)f.size()) {
Q[i] = {mint(0), -f[i]};
} else {
Q[i] = {mint(0)};
}
}
int cur_n = n;
while (cur_n > 0) {
auto R = Q;
for (int i = 1; i <= cur_n; i += 2) {
for (auto& val : R[i]) val = -val;
}
int width = 1;
while(width < 2 * k + 2) width <<= 1;
auto flat_P = pack(P, cur_n + 1, width);
auto flat_Q = pack(Q, cur_n + 1, width);
auto flat_R = pack(R, cur_n + 1, width);
auto flat_S = convolution(flat_P, flat_R);
auto flat_T = convolution(flat_Q, flat_R);
int next_n = cur_n / 2;
int next_k = k * 2;
int parity = cur_n % 2;
vector<fps> next_P(next_n + 1);
for(int i = 0; i <= next_n; ++i) {
int target_idx = 2 * i + parity;
int start = target_idx * width;
if(start >= (int)flat_S.size()) continue;
int len = min((int)flat_S.size() - start, width);
len = min(len, next_k + 1);
next_P[i].resize(len);
for(int j=0; j<len; ++j) next_P[i][j] = flat_S[start+j];
}
vector<fps> next_Q(next_n + 1);
for(int i = 0; i <= next_n; ++i) {
int target_idx = 2 * i;
int start = target_idx * width;
if(start >= (int)flat_T.size()) continue;
int len = min((int)flat_T.size() - start, width);
len = min(len, next_k + 1);
next_Q[i].resize(len);
for(int j=0; j<len; ++j) next_Q[i][j] = flat_T[start+j];
}
P = next_P;
Q = next_Q;
cur_n /= 2;
k *= 2;
}
auto p_poly = P[0];
auto q_poly = Q[0];
p_poly.resize(n + 1, mint(0));
q_poly.resize(n + 1, mint(0));
auto inv_q = poly_inv(q_poly, n);
auto res = mul_trunc(p_poly, inv_q, n);
res.resize(n + 1);
return res;
}
int main() {
int n,a,b;
cin >> n >> a >> b;
ll ans = a;
for(int i = 0; i < n; i++){
cout << ans << endl;
ans = (ans * b);
}
}