結果

問題 No.3174 勝ち残りじゃんけん
ユーザー ymm-knight
提出日時 2025-06-11 21:36:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 276 ms / 2,000 ms
コード長 2,162 bytes
コンパイル時間 2,451 ms
コンパイル使用メモリ 196,152 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-06-11 21:36:15
合計ジャッジ時間 4,818 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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); }

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

ll inv_2k_2[N], e_red[N];

void init()
{
	fci[0] = fct[0] = 1;
	Loop (i,1,N) {
		fct[i] = fct[i-1] * i % mod;
		fci[i] = inv(fct[i]);
	}
	// P[reduce] = 3 * (2^k - 2) / 3^k
	// E[till reduce] = 1/p
	Loop (k,0,N) {
		e_red[k] = inv(3 * (pw(2, k) + mod - 2) * inv(pw(3, k)));
		inv_2k_2[k] = inv(pw(2, k) - 2);
	}
}

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

ll dp_p[N], dp_e[N], dp[N];

void solve()
{
	int n;
	cin >> n;
	dp_p[n] = 1;
	dp_e[n] = 0;
	LoopR (k,1,n) {
		Looc (j,k+1,n) {
			// P[to k] | P[red] = P[to k and red] / P[red] = P[to k] / P[red] = (3 * C(j, k) / 3^j) / (3 * (2^j - 2) / 3^j)
			ll p_to_k = C(j, k) * inv_2k_2[j] % mod;
			ll p = dp_p[j] * p_to_k % mod;
			ll e = (dp_e[j] * p_to_k + e_red[j] * p) % mod;

			debug {
				cerr << k << " <- " << j << ":\n";
				cerr << "p = " << p << '\n';
				cerr << "e = " << e << '\n';
				cerr << '\n';
			}

			dp_p[k] = (dp_p[k] + p) % mod;

			dp_e[k] = (dp_e[k] + e) % mod;

			dp[k] = (dp[k] + e) % mod;
			dp[j] = (dp[j] + mod - e) % mod;

		}
	}
	Loop (i,1,n) {
		dp[i+1] += dp[i];
		dp[i+1] %= mod;
	}
	debug {
		Looc (i,1,n)
			cerr << dp_p[i] << ' ';
		cerr << '\n';
		Looc (i,1,n)
			cerr << dp_e[i] << ' ';
		cerr << '\n';
	}
	Looc (i,1,n)
		cout << dp[i] % mod << ' ';
	cout << '\n';
}

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