結果
| 問題 |
No.1875 Flip Cards
|
| コンテスト | |
| ユーザー |
 Nachia
|
| 提出日時 | 2022-03-11 23:46:08 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 9,862 bytes |
| コンパイル時間 | 1,549 ms |
| コンパイル使用メモリ | 95,712 KB |
| 最終ジャッジ日時 | 2025-01-28 09:09:41 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 WA * 1 |
| other | AC * 1 WA * 6 |
ソースコード
#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;