题解 | #Auspiciousness I#

B. Auspiciousness

考虑直接枚举，求出至少猜对到第 个卡片的方案数，这样将这些方案数全部加起来就是答案。

• 对于第 张牌（）， 若上一张 ，则当前张 大于 上一张； 若上一张 ，则当前张 小于 上一张。

将点数划分为两个集合： （小值），（大值）。

满足上述条件的序列具有以下分段单调性质：

• 连续的属于 的牌构成一个严格递增段（因为每次都要“更大”）。
• 连续的属于 的牌构成一个严格递减段（因为每次都要“更小”）。
• 段与 段必然交替出现（一个 段之后只能接 段，反之亦然）。

记前 张牌中 的个数为 ， 的个数为 ，则 。 设这些牌被分成若干个极长同色段，其中 段有 个， 段有 个。 由于交替性，，且：

• 若 ：可以以 开头，也可以以 开头 → 2 种方向。
• 若 ：只能以 开头，以 结尾。
• 若 ：只能以 开头，以 结尾。

且如果前面一个段是情况 1，那么后一个段一定是情况 2，反之亦然。

由于 最大只有 ，考虑继续枚举，设前面 个元素中 的元素个数为 ， 的元素个数为 ，。

那么就可以数了，至少猜对到第 个卡片的方案数就是：

其中 是第二类斯特林数。

复杂度 。

int n; mint S[N][N], C[N][N], fac[N];
inline void clear() {
    C[0][0] = 0, S[0][0] = 0;
    fac[0] = 0;
    forn (i, 1, n * 2) fac[i] = 0;
    forn (i, 1, n * 2) {
        C[i][0] =0;
        forn (k, 1, i) 
            S[i][k] = C[i][k] = 0;
    }
}
inline void solve() {
    cin >> n >> Mod;
    C[0][0] = 1, S[0][0] = 1;
    fac[0] = 1;
    forn (i, 1, n * 2) fac[i] = fac[i - 1] * mint(i);
    forn (i, 1, n * 2) {
        C[i][0] = 1;
        forn (k, 1, i) 
            S[i][k] = mint(k) * S[i - 1][k] + S[i - 1][k - 1],
            C[i][k] = C[i - 1][k - 1] + C[i - 1][k];
    }
    mint ans = 0;
    forn (i, 1, n * 2 - 1) {
        mint lst = ans;
        forn (up, max(0, i - n), min(n, i)) {
            int dn = i - up;
            mint coef = C[n][up] * C[n][dn] * fac[n * 2 - i];
            forn (g, 1, max(up, dn)) {
                if (up >= g && dn >= g - 1)
                    ans += coef * S[up][g] * S[dn][g - 1] * fac[g] * fac[g - 1];
                if (up >= g - 1 && dn >= g)
                    ans += coef * S[up][g - 1] * S[dn][g] * fac[g] * fac[g - 1];
                if (up >= g && dn >= g)
                    ans += coef * S[up][g] * S[dn][g] * mint(2) * fac[g] * fac[g];
            }
        }
    }
    ans += fac[2 * n];
    cout << ans.r << '\n';
}