結果

問題 No.2004 Incremental Coins
ユーザー sigma425
提出日時 2022-07-10 18:08:06
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 728 ms / 2,000 ms
コード長 10,397 bytes
コンパイル時間 2,707 ms
コンパイル使用メモリ 217,784 KB
最終ジャッジ日時 2025-01-30 06:13:20
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
#define rep(i,n) for(int i=0;i<int(n);i++)
#define rep1(i,n) for(int i=1;i<=int(n);i++)
#define per(i,n) for(int i=int(n)-1;i>=0;i--)
#define per1(i,n) for(int i=int(n);i>0;i--)
#define all(c) c.begin(),c.end()
#define si(x) int(x.size())
#define pb push_back
#define eb emplace_back
#define fs first
#define sc second
template<class T> using V = vector<T>;
template<class T> using VV = vector<vector<T>>;
template<class T,class U> bool chmax(T& x, U y){
    if(x<y){ x=y; return true; }
    return false;
}
template<class T,class U> bool chmin(T& x, U y){
    if(y<x){ x=y; return true; }
    return false;
}
template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
template<class T> int lwb(const V<T>& v, const T& a){return lower_bound(all(v),a) - v.begin();}
template<class T>
V<T> Vec(size_t a) {
    return V<T>(a);
}
template<class T, class... Ts>
auto Vec(size_t a, Ts... ts) {
  return V<decltype(Vec<T>(ts...))>(a, Vec<T>(ts...));
}
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
    return o<<"("<<p.fs<<","<<p.sc<<")";
}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
    o<<"{";
    for(const T& v:vc) o<<v<<",";
    o<<"}";
    return o;
}
constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n-1); }
#ifdef LOCAL
#define show(x) cerr << "LINE" << __LINE__ << " : " << #x << " = " << (x) << endl
void dmpr(ostream& os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
    os<<t<<" ~ ";
    dmpr(os,args...);
}
#define shows(...) cerr << "LINE" << __LINE__ << " : ";dmpr(cerr,##__VA_ARGS__)
#define dump(x) cerr << "LINE" << __LINE__ << " : " << #x << " = {";  \
    for(auto v: x) cerr << v << ","; cerr << "}" << endl;
#else
#define show(x) void(0)
#define dump(x) void(0)
#define shows(...) void(0)
#endif
template<class D> D divFloor(D a, D b){
    return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0);
}
template<class D> D divCeil(D a, D b) {
    return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0);
}
template<unsigned int mod_>
struct ModInt{
    using uint = unsigned int;
    using ll = long long;
    using ull = unsigned long long;
    constexpr static uint mod = mod_;
    uint v;
    ModInt():v(0){}
    ModInt(ll _v):v(normS(_v%mod+mod)){}
    explicit operator bool() const {return v!=0;}
    static uint normS(const uint &x){return (x<mod)?x:x-mod;}       // [0 , 2*mod-1] -> [0 , mod-1]
    static ModInt make(const uint &x){ModInt m; m.v=x; return m;}
    ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));}
    ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));}
    ModInt operator-() const { return make(normS(mod-v)); }
    ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);}
    ModInt operator/(const ModInt& b) const { return *this*b.inv();}
    ModInt& operator+=(const ModInt& b){ return *this=*this+b;}
    ModInt& operator-=(const ModInt& b){ return *this=*this-b;}
    ModInt& operator*=(const ModInt& b){ return *this=*this*b;}
    ModInt& operator/=(const ModInt& b){ return *this=*this/b;}
    ModInt& operator++(int){ return *this=*this+1;}
    ModInt& operator--(int){ return *this=*this-1;}
    template<class T> friend ModInt operator+(T a, const ModInt& b){ return (ModInt(a) += b);}
    template<class T> friend ModInt operator-(T a, const ModInt& b){ return (ModInt(a) -= b);}
    template<class T> friend ModInt operator*(T a, const ModInt& b){ return (ModInt(a) *= b);}
    template<class T> friend ModInt operator/(T a, const ModInt& b){ return (ModInt(a) /= b);}
    ModInt pow(ll p) const {
        if(p<0) return inv().pow(-p);
        ModInt a = 1;
        ModInt x = *this;
        while(p){
            if(p&1) a *= x;
            x *= x;
            p >>= 1;
        }
        return a;
    }
    ModInt inv() const {        // should be prime
        return pow(mod-2);
    }
    // ll extgcd(ll a,ll b,ll &x,ll &y) const{
    //  ll p[]={a,1,0},q[]={b,0,1};
    //  while(*q){
    //      ll t=*p/ *q;
    //      rep(i,3) swap(p[i]-=t*q[i],q[i]);
    //  }
    //  if(p[0]<0) rep(i,3) p[i]=-p[i];
    //  x=p[1],y=p[2];
    //  return p[0];
    // }
    // ModInt inv() const {
    //  ll x,y;
    //  extgcd(v,mod,x,y);
    //  return make(normS(x+mod));
    // }
    bool operator==(const ModInt& b) const { return v==b.v;}
    bool operator!=(const ModInt& b) const { return v!=b.v;}
    bool operator<(const ModInt& b) const { return v<b.v;}
    friend istream& operator>>(istream &o,ModInt& x){
        ll tmp;
        o>>tmp;
        x=ModInt(tmp);
        return o;
    }
    friend ostream& operator<<(ostream &o,const ModInt& x){ return o<<x.v;}
};
using mint = ModInt<998244353>;
//using mint = ModInt<1000000007>;
V<mint> fact,ifact,invs;
mint Choose(int a,int b){
    if(b<0 || a<b) return 0;
    return fact[a] * ifact[b] * ifact[a-b];
}
void InitFact(int N){   //[0,N]
    N++;
    fact.resize(N);
    ifact.resize(N);
    invs.resize(N);
    fact[0] = 1;
    rep1(i,N-1) fact[i] = fact[i-1] * i;
    ifact[N-1] = fact[N-1].inv();
    for(int i=N-2;i>=0;i--) ifact[i] = ifact[i+1] * (i+1);
    rep1(i,N-1) invs[i] = fact[i-1] * ifact[i];
}
// inplace_fmt (without bit rearranging)
// fft:
//      a[rev(i)] <- \sum_j \zeta^{ij} a[j]
// invfft:
//      a[i] <- (1/n) \sum_j \zeta^{-ij} a[rev(j)]
// These two are inversions.
// !!! CHANGE IF MOD is unusual !!!
const int ORDER_2_MOD_MINUS_1 = 23; // ord_2 (mod-1)
const mint PRIMITIVE_ROOT = 3; // primitive root of (Z/pZ)*
void fft(V<mint>& a){
    static constexpr uint mod = mint::mod;
    static constexpr uint mod2 = mod + mod;
    static const int H = ORDER_2_MOD_MINUS_1;
    static const mint root = PRIMITIVE_ROOT;
    static mint magic[H-1];
    int n = si(a);
    assert(!(n & (n-1))); assert(n >= 1); assert(n <= 1<<H);    // n should be power of 2
    if(!magic[0]){      // precalc
        rep(i,H-1){
            mint w = -root.pow(((mod-1)>>(i+2))*3);
            magic[i] = w;
        }
    }
    int m = n;
    if(m >>= 1){
        rep(i,m){
            uint v = a[i+m].v;                  // < M
            a[i+m].v = a[i].v + mod - v;        // < 2M
            a[i].v += v;                        // < 2M
        }
    }
    if(m >>= 1){
        mint p = 1;
        for(int h=0,s=0; s<n; s += m*2){
            for(int i=s;i<s+m;i++){
                uint v = (a[i+m] * p).v;        // < M
                a[i+m].v = a[i].v + mod - v;    // < 3M
                a[i].v += v;                    // < 3M
            }
            p *= magic[__builtin_ctz(++h)];
        }
    }
    while(m){
        if(m >>= 1){
            mint p = 1;
            for(int h=0,s=0; s<n; s += m*2){
                for(int i=s;i<s+m;i++){
                    uint v = (a[i+m] * p).v;        // < M
                    a[i+m].v = a[i].v + mod - v;    // < 4M
                    a[i].v += v;                    // < 4M
                }
                p *= magic[__builtin_ctz(++h)];
            }
        }
        if(m >>= 1){
            mint p = 1;
            for(int h=0,s=0; s<n; s += m*2){
                for(int i=s;i<s+m;i++){
                    uint v = (a[i+m] * p).v;                                // < M
                    a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M
                    a[i+m].v = a[i].v + mod - v;                            // < 3M
                    a[i].v += v;                                            // < 3M
                }
                p *= magic[__builtin_ctz(++h)];
            }
        }
    }
    rep(i,n){
        a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v;     // < 2M
        a[i].v = (a[i].v >= mod) ? a[i].v - mod : a[i].v;       // < M
    }
    // finally < mod !!
}
void invfft(V<mint>& a){
    static constexpr uint mod = mint::mod;
    static constexpr uint mod2 = mod + mod;
    static const int H = ORDER_2_MOD_MINUS_1;
    static const mint root = PRIMITIVE_ROOT;
    static mint magic[H-1];
    int n = si(a);
    assert(!(n & (n-1))); assert(n >= 1); assert(n <= 1<<H);    // n should be power of 2
    if(!magic[0]){      // precalc
        rep(i,H-1){
            mint w = -root.pow(((mod-1)>>(i+2))*3);
            magic[i] = w.inv();
        }
    }
    int m = 1;
    if(m < n>>1){
        mint p = 1;
        for(int h=0,s=0; s<n; s += m*2){
            for(int i=s;i<s+m;i++){
                ull x = a[i].v + mod - a[i+m].v;    // < 2M
                a[i].v += a[i+m].v;                 // < 2M
                a[i+m].v = (p.v * x) % mod;         // < M
            }
            p *= magic[__builtin_ctz(++h)];
        }
        m <<= 1;
    }
    for(;m < n>>1; m <<= 1){
        mint p = 1;
        for(int h=0,s=0; s<n; s+= m*2){
            for(int i=s;i<s+(m>>1);i++){
                ull x = a[i].v + mod2 - a[i+m].v;   // < 4M
                a[i].v += a[i+m].v;                 // < 4M
                a[i].v = (a[i].v >= mod2) ? a[i].v - mod2 : a[i].v; // < 2M
                a[i+m].v = (p.v * x) % mod;     // < M
            }
            for(int i=s+(m>>1); i<s+m; i++){
                ull x = a[i].v + mod - a[i+m].v;    // < 2M
                a[i].v += a[i+m].v; // < 2M
                a[i+m].v = (p.v * x) % mod; // < M
            }
            p *= magic[__builtin_ctz(++h)];
        }
    }
    if(m < n){
        rep(i,m){
            uint x = a[i].v + mod2 - a[i+m].v;  // < 4M
            a[i].v += a[i+m].v; // < 4M
            a[i+m].v = x;   // < 4M
        }
    }
    const mint in = mint(n).inv();
    rep(i,n) a[i] *= in;    // < M
    // finally < mod !!
}
// A,B = 500000 -> 70ms
// verify https://judge.yosupo.jp/submission/44937
V<mint> multiply(V<mint> a, V<mint> b) {
    int A = si(a), B = si(b);
    if (!A || !B) return {};
    int n = A+B-1;
    int s = 1; while(s<n) s*=2;
    if(a == b){         // # of fft call : 3 -> 2
        a.resize(s); fft(a);
        rep(i,s) a[i] *= a[i];
    }else{
        a.resize(s); fft(a);
        b.resize(s); fft(b);
        rep(i,s) a[i] *= b[i];
    }
    invfft(a); a.resize(n);
    return a;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);        //DON'T USE scanf/printf/puts !!
    cout << fixed << setprecision(20);
    InitFact(500010);
    int N; ll K; cin >> N >> K; N++;
    V<mint> A(N); rep(i,N) cin >> A[i];
    VV<int> G(N);
    rep1(i,N-1){
        int p; cin >> p;
        G[p].pb(i);
    }
    V<int> dep(N);
    per(i,N) for(int j: G[i]) chmax(dep[i],dep[j]+1);
    V<mint> ans(N);
    V<deque<mint>> s(N); // first
    VV<mint> t(N);       // last
    auto dfs1 = [&](auto& self,int v) -> void{
        if(G[v].empty()){
            s[v].push_back(A[v]);
            return;
        }
        for(int u: G[v]) self(self,u);
        int heavy = G[v][0];
        for(int u: G[v]) if(dep[u] > dep[heavy]) heavy = u;
        swap(s[v],s[heavy]);
        for(int u: G[v]) if(u != heavy){
            rep(i,si(s[u])) s[v][i] += s[u][i];
        }
        s[v].push_front(A[v]);
    };
    dfs1(dfs1,0);
    auto dfs = [&](auto& self,int v,deque<mint>& deq) -> void{
        if(deq.empty()){
            int n = si(s[v]);
            V<mint> f(n); rep(i,n) f[i] = s[v][i];
            V<mint> g(n);
            {
                mint C = 1;
                rep(i,n){
                    g[i] = C;
                    C *= K-i;
                    C *= invs[i+1];
                }
                show(g);
                reverse(all(g));
            }
            auto h = multiply(f,g);
            t[v].resize(n);
            rep(i,n) t[v][i] = h[n-1+i];
            deq.resize(n);
            rep(i,n) deq[i] = t[v][i];
        }
        show(si(deq));
        show(v);
        show(deq[0]);
        show("--------");
        ans[v] = deq[0];
        deq.pop_front();
        if(G[v].empty()) return;
        int heavy = G[v][0];
        for(int u: G[v]) if(dep[u] > dep[heavy]) heavy = u;
        for(int u: G[v]) if(u != heavy){
            deque<mint> _;
            self(self,u,_);
            rep(i,dep[u]+1) deq[i] -= t[u][i];
        }
        self(self,heavy,deq);
    };
    deque<mint> _;
    dfs(dfs,0,_);
    rep(v,N) cout << ans[v] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0