Submission #19000685

---

Source Code Expand

//Awwawa! Dis cold yis ratten buy tEMMIE!
#include <bits/stdc++.h>
#define ll long long
#define maxn 305 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
const int N = 42;
int dp[N][N][N][N][N];
ll inv[maxn];
int n, k;
ll solve(int rd, int ls, int rs, int item, int remm) {
	if (dp[rd][ls][rs][item][remm] != -1) 
		return dp[rd][ls][rs][item][remm];
	if (item == 0) return 1;
	int part = 0, rem = 0;
	if (remm > rs) part = 0, rem = remm - rs - 1;
	else part = 1, rem = remm;
	ll ans = 0;
	if (rem == 0) {
		if (part == 0) {
			ll co = item * inv[k - rd] % mod;
			if (co != 1)
				ans = (1 - co) * solve(rd, ls, rs, item, rs) % mod;
		}
		else 
			ans = solve(rd + 1, ls, rs, item, ls + rs + 1);
	} 
	else {
		ll co = item * inv[k - rd] %mod;
		if (part == 0) {
			ans += co * solve(rd, ls - 1, rs, item - 1, rem - 1 + rs + 1);
			ans += (1 - co) * solve(rd, ls, rs, item, rem - 1 + rs + 1);
			ans %= mod;
		} 
		else {
			ans += co * solve(rd, ls, rs - 1, item - 1, rem - 1);
			ans += (1 - co) * solve(rd, ls, rs, item, rem - 1);
			ans %= mod;
		}
	}
	ans %= mod;
	return dp[rd][ls][rs][item][remm] = ans;
}

int main() {
	cin >> n >> k;
	for (int i = 0; i < maxn; i++)
		inv[i] = ksm(i, mod - 2);
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < n; i++) {
		ll cur = 1 - solve(0, i, n - i - 1, k, n);
		cur %= mod;
		if (cur < 0) cur += mod;
		cout << cur << endl;
	}
	return 0;
}

Submission Info

Judge Result