結果

問題 No.1875 Flip Cards
ユーザー 👑 NachiaNachia
提出日時 2022-03-11 23:46:08
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 9,862 bytes
コンパイル時間 1,674 ms
コンパイル使用メモリ 97,424 KB
実行使用メモリ 92,956 KB
最終ジャッジ日時 2023-10-14 09:03:14
合計ジャッジ時間 16,724 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,348 KB
testcase_01 AC 2 ms
4,348 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 AC 2 ms
4,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 


#include <vector>
#include <utility>

namespace nachia{

template<unsigned int MOD>
struct PrimitiveRoot{
    static constexpr unsigned long long powm(unsigned long long a, unsigned long long i) {
        unsigned long long res = 1, aa = a;
        while(i){
            if(i & 1) res = res * aa % MOD;
            aa = aa * aa % MOD;
            i /= 2;
        }
        return res;
    }
    static constexpr bool examine_val(unsigned int g){
        unsigned int t = MOD - 1;
        for(unsigned long long d=2; d*d<=t; d++) 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 get_val(){
        for(unsigned int x=2; x<MOD; x++) if(examine_val(x)) return x;
        return 0;
    }
    static const unsigned int val = get_val();
};

}

#include <iostream>
#include <algorithm>
#include <atcoder/modint>
using namespace std;
using i64 = long long;
using u64 = unsigned long long;
using m32 = atcoder::static_modint<998244353>;
#define rep(i,n) for(int i=0; i<(int)(n); i++)

// a^i mod MOD
template<u64 MOD>
u64 powm(u64 a, u64 i) {
    if (i == 0) return 1;
    u64 r = powm<MOD>(a * a % MOD, i / 2);
    if (i & 1) r = r * a % MOD;
    return r;
}


template<u64 MOD, u64 g>
void NTT(vector<u64>& A) {
    int N = 1;
    while (N < (int)A.size()) N *= 2;
    for (int i = 0, j = 0; j < N; j++) {
        if (i < j) swap(A[i], A[j]);
        for (int k = N >> 1; k > (i ^= k); k >>= 1);
    }
    for (int i = 1; i < N; i <<= 1) {
        u64 q = powm<MOD>(g, (MOD - 1) / i / 2), qj = 1;
        for (int j = 0; j < i; j++) {
            for (int k = j; k < N; k += i * 2) {
                u64 l = A[k];
                u64 r = A[k + i] * qj % MOD;
                A[k] = l + r;
                if (A[k] >= MOD) A[k] -= MOD;
                A[k + i] = l + MOD - r;
                if (A[k + i] >= MOD) A[k + i] -= MOD;
            }
            qj = qj * q % MOD;
        }
    }
}


template<u64 MOD, u64 g>
vector<u64> convolution(const vector<u64>& A, const vector<u64>& B) {
    int Z = 1; while (Z < (int)(A.size() + B.size())) Z *= 2;
    vector<u64> Ax(Z), Bx(Z);
    u64 iZ = powm<MOD>(Z, MOD - 2);
    rep(i, A.size()) Ax[i] = A[i];
    rep(i, B.size()) Bx[i] = B[i];
    NTT<MOD, g>(Ax); NTT<MOD, g>(Bx);
    rep(i, Z) Ax[i] = Ax[i] * Bx[i] % MOD;
    NTT<MOD, g>(Ax);
    reverse(Ax.begin() + 1, Ax.end());
    rep(i, Z) Ax[i] = Ax[i] * iZ % MOD;
    Ax.resize(A.size() + B.size() - 1);
    return move(Ax);
}


template<u64 MOD, u64 g>
vector<u64> powsumFPS(const vector<u64>& A, int n) {
    if (n == 0) { return {}; }
    if (n == 1) { return { 1 }; }
    int N = 1; while (N < n) N *= 2;
    int hN = N / 2;
    vector<u64> hInv = powsumFPS<MOD, g>(A, hN);
    vector<u64> tgA(N, 0);
    for (int i = 0; i < min(N, (int)A.size()); i++) tgA[i] = A[i];
    NTT<MOD, g>(tgA);
    vector<u64> htInv(N, 0);
    for (int i = 0; i < hN; i++) htInv[i] = hInv[i];
    NTT<MOD, g>(htInv);
    vector<u64> R(N);
    for (int i = 0; i < N; i++) R[i] = tgA[i] * htInv[i] % MOD;
    NTT<MOD, g>(R); reverse(R.begin() + 1, R.end());
    for (int i = 0; i < hN; i++) R[i] = R[hN + i];
    for (int i = hN; i < N; i++) R[i] = 0;
    NTT<MOD, g>(R);
    u64 iNN = powm<MOD>((u64)N * N % MOD, MOD - 2);
    for (int i = 0; i < N; i++) R[i] = R[i] * htInv[i] % MOD * iNN % MOD;
    NTT<MOD, g>(R); reverse(R.begin() + 1, R.end());
    hInv.resize(n, 0);
    for (int i = hN; i < n; i++) hInv[i] = R[i - hN];
    return move(hInv);
}


template<u64 MOD, u64 g>
vector<u64> invFPS(const vector<u64>& A, int n) {
    u64 iA0 = powm<MOD>(A[0], MOD - 2);
    vector<u64> xA(min(n, (int)A.size()));
    for (int i = 0; i < (int)xA.size(); i++) xA[i] = (MOD - A[i]) * iA0 % MOD;
    xA[0] = 0;
    xA = powsumFPS<MOD, g>(xA, n);
    for (int i = 0; i < (int)xA.size(); i++) xA[i] = xA[i] * iA0 % MOD;
    return move(xA);
}


static vector<u64> InvMOD = { 1,1 };

template<u64 MOD, u64 g>
vector<u64> logFPS(const vector<u64>& A, int n) {
    int z = A.size();
    for (int i = InvMOD.size(); i <= n; i++) {
        InvMOD.push_back((MOD - MOD / i) * InvMOD[MOD % i] % MOD);
    }
    auto res = invFPS<MOD, g>(A, n);
    vector<u64> Abuf(z);
    rep(i, z - 1) Abuf[i] = A[i + 1] * (i + 1) % MOD;
    res = convolution<MOD, g>(res, Abuf);
    res.resize(n);
    for (int i = n - 2; i >= 0; i--) res[i + 1] = res[i] * InvMOD[i + 1] % MOD;
    res[0] = 0;
    return res;
}


template<u64 MOD, u64 g>
vector<u64> expFPS(const vector<u64>& A, int n) {
    vector<u64> res = { 1 };
    while ((int)res.size() < n) {
        int z = res.size();
        auto tmp = logFPS<MOD, g>(res, z * 2);
        tmp[0] = MOD - 1;
        rep(i, min<int>(z * 2, A.size())) {
            tmp[i] = MOD - tmp[i] + A[i];
            if (tmp[i] >= MOD) tmp[i] -= MOD;
        }
        res = convolution<MOD, g>(res, tmp);
        res.resize(min(n, 2 * z));
    }
    return res;
}


template<u64 MOD, u64 g>
vector<u64> powFPS(const vector<u64>& A, u64 k) {
    int n = A.size();
    int zerocnt = 0;
    rep(i, n) if (A[i] == 0) zerocnt = i + 1; else break;
    if (zerocnt >= (n - 1) / k + 1) return vector<u64>(n, 0);
    auto res = A;
    rep(i, n - zerocnt) res[i] = res[i + zerocnt];
    i64 A0 = res[0];
    i64 iA0 = powm<MOD>(A0, MOD - 2);
    i64 pA0 = powm<MOD>(A0, k);
    rep(i, n) res[i] = res[i] * iA0 % MOD;
    res = logFPS<MOD, g>(res, n);
    rep(i, n) res[i] = res[i] * k % MOD;
    res = expFPS<MOD, g>(res, n);
    rep(i, n) res[i] = res[i] * pA0 % MOD;
    zerocnt *= k;
    res.resize(n);
    for (int i = n - 1; i >= zerocnt; i--) res[i] = res[i - zerocnt];
    rep(i, zerocnt) res[i] = 0;
    return res;
}



template<u64 MOD, u64 g>
vector<u64> SubsetSum(const vector<u64>& D) {
    int n = D.size();
    for (int i = InvMOD.size(); i <= n; i++) {
        InvMOD.push_back((MOD - MOD / i) * InvMOD[MOD % i] % MOD);
    }
    vector<u64> A(n);
    for (int i = 1; i < n; i++) if (D[i] != 0) {
        u64 tmp = i * D[i] % MOD;
        for (int a = i; a < n; a += i) {
            A[a] = (A[a] + tmp * InvMOD[a]) % MOD;
            tmp = MOD - tmp;
        }
    }
    rep(i, n + 1) A[i] %= MOD;
    A = expFPS<MOD, g>(A, n);
    return A;
}


template<u64 MOD, u64 g>
vector<u64> PolynomialTaylorShift(vector<u64> A, u64 c){
    u64 n = A.size();

    vector<u64> factorial(n+1, 1);
    for(u64 i=1; i<=n; i++) factorial[i] = ((u64)factorial[i-1] * i) % MOD;
    vector<u64> invfactorial(n+1, 1);
    invfactorial[n] = powm<MOD>(factorial[n], MOD-2);
    for(u64 i=n; i>=1; i--) invfactorial[i-1] = ((u64)invfactorial[i] * i) % MOD;

    vector<u64> C(n, 1);
    for(u64 i=1; i<n; i++) C[i] = (u64)C[i-1] * c % MOD;
    for(u64 i=1; i<n; i++) C[i] = (u64)C[i] * invfactorial[i] % MOD;
    reverse(C.begin(), C.end());
    for(u64 i=1; i<n; i++) A[i] = (u64)A[i] * factorial[i] % MOD;
    A = convolution<MOD, g>(A, C);
    for(u64 i=0; i<n; i++) A[i] = (u64)A[n-1+i] * invfactorial[i] % MOD;
    A.resize(n);
    return A;
}


// NTT Mod List !!
// <469762049,3>
// <998244353,3>
// <1107296257,10>
// <2113929217,5>


const int INF = 1001001;
const u64 MOD = 998244353;
const u64 g = nachia::PrimitiveRoot<MOD>::val;

int main(){
    int N,M; cin >> N >> M;
    vector<u64> A(N);
    vector<u64> B(N);
    vector<u64> C(N);
    rep(i,N) cin >> A[i] >> B[i] >> C[i];

    u64 off = 1;
    rep(i,N) off *= powm<MOD>(A[i], C[i]);
    rep(i,N) B[i] = B[i] * powm<MOD>(A[i], MOD-2) % MOD;

    vector<u64> fact(M+1, 1);
    for(int i=1; i<=M; i++) fact[i] = fact[i-1] * i % MOD;
    vector<u64> ifact(M+1, 1);
    ifact[M] = powm<MOD>(fact[M], MOD-2);
    for(int i=M; i>=1; i--) ifact[i-1] = ifact[i] * i % MOD;
    vector<u64> inv(M+1, 1);
    for(int i=1; i<=M; i++) inv[i] = ifact[i] * fact[i-1] % MOD;

    vector<u64> ExK;

    {
        vector<vector<u64>> Fup, Fdown;
        rep(i,N){
            Fup.push_back(vector<u64>{ B[i] * C[i] % MOD });
            Fdown.push_back(vector<u64>{ u64(1), B[i] });
        }
        for(int i=0; i+1<(int)Fup.size(); i += 2){
            vector<u64> u1 = convolution<MOD, g>(Fup[i], Fdown[i+1]);
            vector<u64> u2 = convolution<MOD, g>(Fup[i+1], Fdown[i]);
            if(u1.size() < u2.size()) swap(u1, u2);
            rep(i,u2.size()) u1[i] = (u1[i] + u2[i]) % MOD;
            Fdown.push_back(convolution<MOD, g>(Fdown[i], Fdown[i+1]));
            Fup.push_back(move(u1));
        }

        auto Frac = convolution<MOD, g>(Fup.back(), invFPS<MOD, g>(Fdown.back(), M+1));
        
        Frac.resize(M+1, 0);
        for(int i=M; i>=1; i--) Frac[i] = Frac[i-1] * inv[i] % MOD;
        Frac[0] = 0;

        ExK = expFPS<MOD, g>(Frac, M+1);
    }

    ExK = PolynomialTaylorShift<MOD, g>(ExK, MOD - 1);

    {
        vector<vector<u64>> Fup, Fdown;
        rep(i,M+1){
            Fup.push_back(vector<u64>{ ExK[i] });
            Fdown.push_back(vector<u64>{ u64(1), (MOD-i) % MOD });
        }
        for(int i=0; i+1<(int)Fup.size(); i += 2){
            vector<u64> u1 = convolution<MOD, g>(Fup[i], Fdown[i+1]);
            vector<u64> u2 = convolution<MOD, g>(Fup[i+1], Fdown[i]);
            if(u1.size() < u2.size()) swap(u1, u2);
            rep(i,u2.size()) u1[i] = (u1[i] + u2[i]) % MOD;
            Fdown.push_back(convolution<MOD, g>(Fdown[i], Fdown[i+1]));
            Fup.push_back(move(u1));
        }

        ExK = convolution<MOD, g>(Fup.back(), invFPS<MOD, g>(Fdown.back(), M+1));
    }
    
    auto ans = ExK;
    
    rep(i,M+1) ans[i] = ans[i] * off % MOD;
    for(int i=1; i<=M; i++) cout << ans[i] << '\n';

    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0