#1081186 (C++17) No.3169 [Cherry 7th Tune] Desire for Approval

提出ソース
結果

問題	No.3169 [Cherry 7th Tune] Desire for Approval
ユーザー	👑 Nachia
提出日時	2025-05-01 03:15:17
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	4,447 ms / 7,000 ms
コード長	13,027 bytes
コンパイル時間	1,337 ms
コンパイル使用メモリ	91,828 KB
実行使用メモリ	50,304 KB
最終ジャッジ日時	2025-05-30 21:09:22
合計ジャッジ時間	91,372 ms
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 46
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
using i64 = long long;
using u64 = unsigned long long;



#ifdef USE_ATCODER_LIBRARY

#include <atcoder/modint>
using Modint = atcoder::static_modint<998244353>;
#include <atcoder/convolution>

namespace nachia{
    template<class Modint>
    std::vector<Modint> Convolution(
        const std::vector<Modint>& A,
        const std::vector<Modint>& B
    ){
        return atcoder::convolution(A, B);
    }
}

#else

#include <cassert>
namespace nachia{

// ax + by = gcd(a,b)
// return ( x, - )
std::pair<long long, long long> ExtGcd(long long a, long long b){
    long long x = 1, y = 0;
    while(b){
        long long u = a / b;
        std::swap(a-=b*u, b);
        std::swap(x-=y*u, y);
    }
    return std::make_pair(x, a);
}

} // namespace nachia

namespace nachia{

template<unsigned int MOD>
struct StaticModint{
private:
    using u64 = unsigned long long;
    unsigned int x;
public:

    using my_type = StaticModint;
    template< class Elem >
    static Elem safe_mod(Elem x){
        if(x < 0){
            if(0 <= x+MOD) return x + MOD;
            return MOD - ((-(x+MOD)-1) % MOD + 1);
        }
        return x % MOD;
    }

    StaticModint() : x(0){}
    StaticModint(const my_type& a) : x(a.x){}
    StaticModint& operator=(const my_type&) = default;
    template< class Elem >
    StaticModint(Elem v) : x(safe_mod(v)){}
    unsigned int operator*() const { return x; }
    my_type& operator+=(const my_type& r) { auto t = x + r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator+(const my_type& r) const { my_type res = *this; return res += r; }
    my_type& operator-=(const my_type& r) { auto t = x + MOD - r.x; if(t >= MOD) t -= MOD; x = t; return *this; }
    my_type operator-(const my_type& r) const { my_type res = *this; return res -= r; }
    my_type operator-() const noexcept { my_type res = *this; res.x = ((res.x == 0) ? 0 : (MOD - res.x)); return res; }
    my_type& operator*=(const my_type& r){ x = (u64)x * r.x % MOD; return *this; }
    my_type operator*(const my_type& r) const { my_type res = *this; return res *= r; }
    bool operator==(const my_type& r) const { return x == r.x; }
    my_type pow(unsigned long long i) const {
        my_type a = *this, res = 1;
        while(i){ if(i & 1){ res *= a; } a *= a; i >>= 1; }
        return res;
    }
    my_type inv() const { return my_type(ExtGcd(x, MOD).first); }
    unsigned int val() const { return x; }
    int hval() const { return int(x > MOD/2 ? x - MOD : x); }
    static constexpr unsigned int mod() { return MOD; }
    static my_type raw(unsigned int val) { auto res = my_type(); res.x = val; return res; }
    my_type& operator/=(const my_type& r){ return operator*=(r.inv()); }
    my_type operator/(const my_type& r) const { return operator*(r.inv()); }
};

} // namespace nachia
using Modint = nachia::StaticModint<998244353>;

namespace nachia{

template<unsigned int MOD>
struct PrimitiveRoot{
    using u64 = unsigned long long;
    static constexpr u64 powm(u64 a, u64 i) {
        u64 res = 1, aa = a;
        for( ; i; i /= 2){
            if(i & 1) res = res * aa % MOD;
            aa = aa * aa % MOD;
        }
        return res;
    }
    static constexpr bool ExamineVal(unsigned int g){
        u64 t = MOD - 1;
        for(u64 d=2; d*d<=t; d+=1+(d&1)) if(t % d == 0){
            if(powm(g, (MOD - 1) / d) == 1) return false;
            while(t % d == 0) t /= d;
        }
        if(t != 1) if(powm(g, (MOD - 1) / t) == 1) return false;
        return true;
    }
    static constexpr unsigned int GetVal(){
        for(u64 x=2; x<MOD; x++) if(ExamineVal(x)) return x;
        return 0;
    }
    static const unsigned int val = GetVal();
};

} // namespace nachia

namespace nachia{

int Popcount(unsigned long long c) noexcept {
#ifdef __GNUC__
    return __builtin_popcountll(c);
#else
    c = (c & (~0ull/3)) + ((c >> 1) & (~0ull/3));
    c = (c & (~0ull/5)) + ((c >> 2) & (~0ull/5));
    c = (c & (~0ull/17)) + ((c >> 4) & (~0ull/17));
    c = (c * (~0ull/257)) >> 56;
    return c;
#endif
}

// please ensure x != 0
int MsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return 63 - __builtin_clzll(x);
#else
    using u64 = unsigned long long;
    int q = (x >> 32) ? 32 : 0;
    auto m = x >> q;
    constexpr u64 hi = 0x88888888;
    constexpr u64 mi = 0x11111111;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 35;
    m = (((m | ~(hi - (m & ~hi))) & hi) * mi) >> 31;
    q += (m & 0xf) << 2;
    q += 0x3333333322221100 >> (((x >> q) & 0xf) << 2) & 0xf;
    return q;
#endif
}

// please ensure x != 0
int LsbIndex(unsigned long long x) noexcept {
#ifdef __GNUC__
    return __builtin_ctzll(x);
#else
    return MsbIndex(x & -x);
#endif
}

}


namespace nachia {

template<class mint>
struct NttInterface{

template<class Iter>
void Butterfly(Iter, int) const {}

template<class Iter>
void IButterfly(Iter, int) const {}

template<class Iter>
void BitReversal(Iter a, int N) const {
    for(int i=0, j=0; j<N; j++){
        if(i < j) std::swap(a[i], a[j]);
        for(int k = N>>1; k > (i^=k); k>>=1);
    }
}

};

} // namespace nachia
#include <iterator>
#include <array>

namespace nachia{

template <class mint>
struct Ntt : NttInterface<mint> {

using u32 = unsigned int;
using u64 = unsigned long long;
    
static int ceil_pow2(int n) {
    int x = 0;
    while ((1U << x) < (u32)(n)) x++;
    return x;
}
    
static constexpr int bsf_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

struct fft_info {
    static constexpr u32 g = nachia::PrimitiveRoot<mint::mod()>::val;
    static constexpr int rank2 = bsf_constexpr(mint::mod()-1);
    using RootTable = std::array<mint, rank2+1>;
    RootTable root, iroot, rate3, irate3;

    fft_info(){
        root[rank2] = mint(g).pow((mint::mod() - 1) >> rank2);
        iroot[rank2] = root[rank2].inv();
        for(int i=rank2-1; i>=0; i--){
            root[i] = root[i+1] * root[i+1];
            iroot[i] = iroot[i+1] * iroot[i+1];
        }
        mint prod = 1, iprod = 1;
        for(int i=0; i<=rank2-3; i++){
            rate3[i] = root[i+3] * prod;
            irate3[i] = iroot[i+3] * iprod;
            prod *= iroot[i+3];
            iprod *= root[i+3];
        }
    }
};

template<class RandomAccessIterator>
void ButterflyLayered(RandomAccessIterator a, int n, int stride, int repeat) const {
    static const fft_info info;
    int h = n * stride;
    
    while(repeat--){

    int len = 1;
    int p = h;
    if(ceil_pow2(n)%2 == 1){
        p >>= 1;
        for(int i=0; i<p; i++){
            mint l = a[i], r = a[i+p];
            a[i] = l+r; a[i+p] = l-r;
        }
        len <<= 1;
    }
    for( ; p > stride; ){
        p >>= 2;
        mint rot = 1, imag = info.root[2];
        u64 mod2 = u64(mint::mod()) * mint::mod();
        int offset = p;
        for(int s=0; s<len; s++){
            if(s) rot *= info.rate3[LsbIndex(~(u32)(s-1))];
            mint rot2 = rot * rot;
            mint rot3 = rot2 * rot;
            for(int i=offset-p; i<offset; i++){
                u64 a0 = u64(a[i].val());
                u64 a1 = u64(a[i+p].val()) * rot.val();
                u64 a2 = u64(a[i+2*p].val()) * rot2.val();
                u64 a3 = u64(a[i+3*p].val()) * rot3.val();
                u64 a1na3imag = u64(mint(a1 + mod2 - a3).val()) * imag.val();
                u64 na2 = mod2 - a2;
                a[i] = a0 + a2 + a1 + a3;
                a[i+1*p] = a0 + a2 + (2 * mod2 - (a1 + a3));
                a[i+2*p] = a0 + na2 + a1na3imag;
                a[i+3*p] = a0 + na2 + (mod2 - a1na3imag);
            }
            offset += p << 2;
        }
        len <<= 2;
    }
    
    a += h;
    }
}

template<class RandomAccessIterator>
void Butterfly(RandomAccessIterator a, int n) const {
    ButterflyLayered(a, n, 1, 1);
}

template<class RandomAccessIterator>
void IButterflyLayered(RandomAccessIterator a, int n, int stride, int repeat) const {

    static const fft_info info;
    constexpr int MOD = mint::mod();
    
    while(repeat--){
    
    int len = n;
    int p = stride;

    for( ; 2 < len; ){
        len >>= 2;
        mint irot = 1, iimag = info.iroot[2];
        int offset = p;
        for(int s=0; s<len; s++){
            if(s) irot *= info.irate3[LsbIndex(~(u32)(s-1))];
            mint irot2 = irot * irot;
            mint irot3 = irot2 * irot;
            for(int i=offset-p; i<offset; i++){
                u64 a0 = a[i].val();
                u64 a1 = a[i+p].val();
                u64 a2 = a[i+2*p].val();
                u64 a3 = a[i+3*p].val();
                u64 a2na3iimag = mint((a2 + MOD - a3) * iimag.val()).val();
                a[i] = a0 + a1 + a2 + a3;
                a[i+p] = (a0 + (MOD - a1) + a2na3iimag) * irot.val();
                a[i+2*p] = (a0 + a1 + (MOD - a2) + (MOD - a3)) * irot2.val();
                a[i+3*p] = (a0 + (MOD - a1) + (MOD - a2na3iimag)) * irot3.val();
            }
            offset += p << 2;
        }
        p <<= 2;
    }
    if(len == 2){
        for(int i=0; i<p; i++){
            mint l = a[i], r = a[i+p];
            a[i] = l+r; a[i+p] = l-r;
        }
        p <<= 1;
    }
    
    a += p;
    }
}

template<class RandomAccessIterator>
void IButterfly(RandomAccessIterator a, int n) const {
    IButterflyLayered(a, n, 1, 1);
}

};

} // namespace nachia

namespace nachia{

template<class Modint>
std::vector<Modint> Convolution(
    const std::vector<Modint>& A,
    const std::vector<Modint>& B
){
    int n = A.size();
    int m = B.size();
    if(n <= 40 || m <= 40){
        if(n+m == 0) return std::vector<Modint>(0);
        std::vector<Modint> C(n+m-1);
        for(int i=0; i<n; i++) for(int j=0; j<m; j++){
            C[i+j] += A[i] * B[j];
        }
        return C;
    }
    int g = 1; while(g < n+m-1) g *= 2;
    std::vector<Modint> C(g);
    for(int i=0; i<n; i++) C[i] = A[i];
    Ntt<Modint> ntt;
    ntt.Butterfly(C.begin(), g);
    std::vector<Modint> D(g);
    for(int i=0; i<m; i++) D[i] = B[i];
    ntt.Butterfly(D.begin(), g);
    Modint w = Modint(g).inv();
    for(int i=0; i<g; i++) C[i] *= D[i] * w;
    ntt.IButterfly(C.begin(), g);
    C.resize(n+m-1);
    return C;
}

} // namespace nachia

#endif


struct ExpPoly {
    std::vector<Modint> A;
    Modint e;

    // x to infty
    ExpPoly indefIntegral(){
        auto B = A;
        ExpPoly res;
        res.e = e;
        Modint ie = e.inv();
        for(int i=int(A.size()-1); i>=0; i--){
            B[i] *= ie;
            if(i) B[i-1] -= B[i] * i;
        }
        for(auto& b : B) b = -b;
        swap(res.A, B);
        return res;
    }

    Modint defIntegral(){
        return indefIntegral().A[0];
    }

    ExpPoly operator*(const ExpPoly& r) const {
        ExpPoly res;
        res.e = e + r.e;
        res.A = nachia::Convolution(A, r.A);
        return res;
    }
};

//string fracformat(Modint x){
//    if(x.val() == 0) return "0";
//    for(int i=1; ; i++){
//        Modint y = x * Modint::raw(i);
//        if(y.val() <= 100000) return to_string(y.val()) + "/" + to_string(i);
//        if(998244353 - y.val() <= 100000) return to_string(int(y.val()) - 998244353) + "/" + to_string(i);
//    }
//}
//void outExpPoly(const ExpPoly& a){
//    cout << "( ";
//    rep(i,a.A.size()){
//        if(i) cout << " + ";
//        cout << fracformat(a.A[i]) << " x^" << i;
//    }
//    cout << " ) e^" << fracformat(a.e) << endl;
//}


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    i64 N; cin >> N;
    vector<ExpPoly> F(N), G(N);
    rep(i,N){
        i64 k, a; cin >> k >> a;
        Modint t =  Modint(a).pow(k);
        for(i64 i=1; i<=k-1; i++) t *= i;
        F[i].A.resize(k);
        F[i].A[k-1] = t.inv();
        F[i].e = -Modint(a).inv();
        G[i] = F[i].indefIntegral();
    }
    vector<ExpPoly> prodG(1<<N);
    prodG[0].A.push_back(1);
    prodG[0].e = 0;
    rep(b,N) rep(i,1<<b) prodG[i|(1<<b)] = prodG[i] * G[b];

    //for(auto a : F){ outExpPoly(a); } cout << endl;
    //for(auto a : G){ outExpPoly(a); } cout << endl;
    //for(auto a : prodG){ outExpPoly(a); } cout << endl;

    vector<Modint> fact(100); fact[0] = 1; rep(i,100) if(i) fact[i] = fact[i-1] * i;
    auto comb = [&](i64 a, i64 b){ return fact[a] / (fact[b] * fact[a-b]); };
    vector<Modint> mp(N);
    rep(s,N) rep(t,1<<N) if(!(t&(1<<s))){
        int pc = __builtin_popcountll(t);
        auto prodGF = prodG[t] * F[s];
        prodGF.A.insert(prodGF.A.begin(), 0);
        Modint q = prodGF.defIntegral();
        //cout << "s = " << s << " , t = " << t << " , q = " << fracformat(q) << endl << "   "; outExpPoly(prodGF);
        mp[N-1-pc] += q;
    }
    for(int i=N-1; i>=0; i--) rep(j,i) mp[i] += mp[j] * comb(N-1-j,N-1-i) * Modint(-1).pow(abs(i-j));
    rep(i,N){
        if(i) cout << " ";
        cout << mp[i].val();
    } cout << endl;
    return 0;
}
yukicoder

結果

ソースコード
