又是久违的 tourist round。。。

Problem D.

• https://zhuanlan.zhihu.com/p/599333683

Problem F – Bracket Insertion

题意

构造一个初始为空的括号序列，执行 n 次插入操作，每次操作任选序列中的一个位置，插入 "()" 或 ")("。
问最终构成的括号序列为合法括号序列的操作方案的概率。

题解

组合计数。
先转换成计数问题，不难发现，对于第 i 次操作，我们有 i*2-1 种插入的位置可供选择，因而求出合法的操作方案总数，处以 1*3*5*...*2n-1 即可。
麻烦的是，我们甚至不能把每次插入的一对括号看成是一个独立的元素，后续插入操作甚至可以从中间破坏它。

回忆 Catalan 序列的做法，虽然和这个题看起来有很大的不同，前者是计数合法的括号序列总数，本题是计数合法的操作方案。
但是依然可以给我们提供许多有益的思路。回忆 Catalan 序列的卷积形递推公式。
我们实际上是考察第一组匹配的括号，然后分别枚举括号内或括号外的括号层数，以进行递归。

这个题是否可以使用同样的策略呢？
我们同样固定第一组括号，那么之后的括号，只会是下述三种情况之一：L(M)R。
因为被初始括号所分割，这里 L M R 的状态都独立的。
这里 L 和 R 的 size 可以合并在一起，这样我们只要枚举 M 的 size 即可。

这样我们就有了类 Catalan 的递推关系，进一步这里的不同时，子状态中并不一定要求是合法的括号序列，
我们需要记录子状态的不合法的等级，也就是前缀和的最小值。

进一步考虑细节，在转移时，我们发现我们只需要考虑前缀和 >= j 的状态，因此可以直接将前缀和定义在状态中。
f[i][j]: 执行了 i 次插入操作，且当前前缀和最小值不小于 -j 的方案数。
我们枚举左右的子树 size 和 a 或中间的子树 size b，得到转移方程：

这里的转移出现了组合数，一个常见的技巧是，我们可以类比 EFG 中的处理方法，对每个状态 f[i][j] 都除以 i! 以简化转移。（然后下标里有 -1 也很烦，不如也 offset 一下。。。）

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

进一步，和 Catalan 序列一样，这个题也可以从树的角度进行思考。
我们设法建立起括号序列与一个有标号森林的一一对应关系（森林也可视为有一个虚根节点的树），
每次操作，我们都相当于按照顺序，插入一个新的有标号的叶子节点（区分孩子的顺序）（祖先的标号一定小于孩子）。

括号的状态对应节点处权值 （1 或 -1），括号序列的前缀和对应树中的一段 dfs 序，也就是根到每一个节点的路径的权值和。
括号序列合法，就是所有这些和都 >= 0。

同样的，在转移过程中，括号序列允许不合法，我们进行同样的加维，只是这里因为我们已经建立了一一对应关系，转移时我们可以直接对这里的树结构进行计数。
我们直接枚举树的形态，再用组合数重新进行标号，得到更简单的转移方程：

注意这里的 b+1 是因为，我们已经把 size 为 b 的森林，和一个新的节点作为了一个完整的子树，连接在虚根节点上。
得到的方程更为简洁。

（当然这两种做法是完全等价的，无论从括号序列的角度分析还是从树的角度分析，只是描述的语言略有不同罢了，都能得到两种转移方程，
区别是我们递归的时候是拎出来考察的是编号为 1 的节点所在的子树，还是位置靠边的一个子树。）

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

Posted by xiaodao
Category: 日常