結果

問題 No.3169 [Cherry 7th Tune] Desire for Approval
ユーザー ymm-knight
提出日時 2025-06-12 22:26:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,724 ms / 7,000 ms
コード長 3,635 bytes
コンパイル時間 2,102 ms
コンパイル使用メモリ 207,736 KB
実行使用メモリ 114,048 KB
最終ジャッジ日時 2025-06-12 22:26:49
合計ジャッジ時間 39,400 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define Loop(x,l,r) for (ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = ll(r)-1; x >= ll(l); --x)
#define Looc(x,l,r) for (ll x = ll(l); x <= ll(r); ++x)
#define LoocR(x,l,r) for (ll x = ll(r); x >= ll(l); --x)
#define int ll
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#ifndef DB
#define DB 0
#define endl '\n'
#endif
#define debugl(l) if constexpr ((l) < DB)
#define debug debugl(0)

const int mod = 998244353;

ll pw(ll x, ll y) {
	ll a = 1;
	x = (x%mod+mod)%mod;
	while (y) {
		if (y%2)
			a = a*x % mod;
		x = x*x % mod;
		y /= 2;
	}
	return a;
}
ll inv(ll x) { return pw(x, mod-2); }

int w[24], wi[24], inv2n[24];

typedef vector<ll> vec;

void ntt(ll *a, int lg, bool inverse = 0)
{
	int n = 1<<lg;

	vector<int> rev(n);
	Loop (i,1,n) {
		rev[i] = (rev[i/2]>>1) ^ ((i&1)<<(lg-1));
		if (i < rev[i])
			swap(a[i], a[rev[i]]);
	}

	Loop (r,1,n+1) {
		int mx = __builtin_ctz(r);
		Loop (lz,0,mx) {
			int len = 1<<lz;
			int l = r - len*2;
			int m = r - len;
			ll wn = (inverse? wi[lz+1]: w[lz+1]);
			ll wc = 1;

			Loop(i,0,len) {
				ll a1 = (a[l+i] +      wc *a[m+i]) % mod;
				ll a2 = (a[l+i] + (mod-wc)*a[m+i]) % mod;
				a[l+i] = a1;
				a[m+i] = a2;
				wc = wc*wn % mod;
			}
		}
	}

	if (inverse) {
		ll x = inv2n[lg];
		Loop (i,0,n)
			a[i] = a[i] * x % mod;
	}
}

vec mul(vec a, vec b)
{
	int n = a.size() + b.size() - 1;
	int lg = __lg(2*n-1);
	int len = 1<<lg;

	a.resize(len);
	b.resize(len);
	ntt(a.data(), lg);
	ntt(b.data(), lg);

	vec ans(len);
	Loop (i,0,len)
		ans[i] = a[i] * b[i] % mod;
	ntt(ans.data(), lg, 1);
	ans.resize(n);

	return ans;
}

const int N = 8192;
ll fct[N], fci[N];

void init()
{
	w[23] = 31;
	LoopR (i,0,23)
		w[i] = w[i+1] * w[i+1] % mod;
	Loop (i,0,24) {
		wi[i] = inv(w[i]);
		inv2n[i] = inv(1ll<<i);
	}

	fci[0] = fct[0] = 1;
	Loop (i,1,N) {
		fct[i] = fct[i-1] * i % mod;
		fci[i] = inv(fct[i]);
	}
}

ll C(int n, int r)
{
	if (r < 0 || r > n)
		return 0;
	return fct[n] * fci[r] % mod * fci[n-r] % mod;
}

struct poly {
	ll lambda;
	vec a;

	ll eval() {
		ll sum = 0;
		ll invi = inv(lambda);
		ll pwi = invi;
		Loop (j,0,a.size()) {
			sum = (sum + a[j] * fct[j] % mod * pwi) % mod;
			pwi = pwi * invi % mod;
		}
		return sum;
	}
};

poly operator*(const poly &a, const poly &b) {
	return {
		(a.lambda + b.lambda) % mod,
		mul(a.a, b.a),
	};
}

void solve()
{
	int n;
	cin >> n;
	vector<int> k(n), a(n);
	Loop (i,0,n)
		cin >> k[i] >> a[i];

	Loop (i,0,n)
		a[i] = inv(a[i]);

	vector<poly> ps(1<<n);
	Loop (pos,0,n) {
		auto &p = ps[1<<pos];
		p.lambda = a[pos];
		p.a.resize(k[pos]);
		Loop (j,0,k[pos])
			p.a[j] = fci[j] * pw(a[pos], j) % mod;
	}

	Loop (msk,1,1<<n) {
		auto lo = msk&-msk;
		auto hi = msk ^ lo;
		if (!hi)
			continue;
		ps[msk] = ps[hi] * ps[lo];
	}

	vector<ll> eval(1<<n);
	eval[0] = 1;
	Loop (msk,1,1<<n)
		eval[msk] = ps[msk].eval();

	vector<ll> ans(n+1);

	Loop (inc_msk,0,1<<n) {
		int bits = __builtin_popcount(inc_msk);
		int ignore = n-bits;
		Loop (ng,0,bits+1) {
			ll x = C(bits, ng) * eval[inc_msk] % mod;
			x = ng%2? mod-x: x;
			debug {
				cerr << ng + ignore << " <- " << x << ": " << bits << ' ' << ng << ' ' << '\n';
			}
			ans[ng + ignore] += x;
			ans[ng + ignore] %= mod;
		}
	}

	Loop (i,0,n)
		ans[i+1] = (ans[i+1] + ans[i]) % mod;

	debug {
		Loop (i,0,n)
			cerr << ps[1<<i].eval() << '\n';
		cerr << '\n';
		cerr << ans[1] * 28 << '\n';
		cerr << '\n';
	}

	Loop (i,0,n)
		cout << ans[i] << ' ';
	cout << '\n';
}

signed main()
{
	init();
	cin.tie(0) -> sync_with_stdio(false);
	int t = 1;
	//cin >> t;
	while (t--)
		solve();
}
0