# 某岛

… : "…アッカリ～ン . .. . " .. .
January 17, 2023

# Problem F – Bracket Insertion

## 题解

f[i][j]: 执行了 i 次插入操作，且当前前缀和最小值不小于 -j 的方案数。

https://codeforces.com/contest/1782/submission/189455837

#include <lastweapon/number>
using namespace lastweapon;
const int N = int(5e2) + 9;
Int f[N][N], f2[N][N], I[2*N], Fact[2*N]; // i step, min pref sum >= -(j-1)
int n; Int p, q;

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

MOD = 998244353;
RD(n); p = Int(RD()) / 10000; q = Int(1) - p;
for (int i=(I[1]=1)+1; i<=2*n; i++) I[i] = 1ll * (MOD - MOD / i) * I[MOD%i] % MOD;
Fact[0] = 1; REP_1(i, n) Fact[i] = Fact[i-1] * i;

REP_1(i, n+1) f2[0][i] = f[0][i] = 1;

// \sum f[a1] * f[a2] * (p*f[b]+q*f[b]) * \binom{i-1}{a, b}
REP_1(i, n) REP_1(j, n-i+1) {
REP(a, i) {
int b = i-1-a;
f[i][j] += f2[a][j] * (p*f[b][j+1] + q*f[b][j-1]);
}
f[i][j] *= I[i];
REP(a, i+1) {
int b = i-a;
f2[i][j] += f[a][j] * f[b][j];
}
}

Int z = f[n][1] * Fact[n]; REP_1(i, n) {
z *= I[i*2-1];
}
cout << z << endl;
}


（当然这两种做法是完全等价的，无论从括号序列的角度分析还是从树的角度分析，只是描述的语言略有不同罢了，都能得到两种转移方程，

https://codeforces.com/contest/1782/submission/189456196

#include <lastweapon/number>
using namespace lastweapon;
const int N = int(5e2) + 9;
Int f[N][N], I[2*N], Fact[2*N]; // i step, min pref sum >= -(j-1)
int n; Int p, q;

int main() {

#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

MOD = 998244353;
RD(n); p = Int(RD()) / 10000; q = Int(1) - p;
for (int i=(I[1]=1)+1; i<=2*n; i++) I[i] = 1ll * (MOD - MOD / i) * I[MOD%i] % MOD;
Fact[0] = 1; REP_1(i, n) Fact[i] = Fact[i-1] * i;

REP_1(i, n+1) f[0][i] = 1;

// \sum f[a] * (p*f[b]+q*f[b]) * \binom{i}{a, b+1}
REP_1(i, n) REP_1(j, n-i+1) {
REP(a, i) {
int b = i-1-a;
f[i][j] += f[a][j] * (p*f[b][j+1] + q*f[b][j-1]) * I[b+1];
}
}

Int z = f[n][1] * Fact[n]; REP_1(i, n) {
z *= I[i*2-1];
}
cout << z << endl;
}