2025.2.17 鮮花

機關題解

MARENOL

要是放這個歌機房會有人能欣賞嗎？？？

來自b站視頻av35346701下的評論

應該是 LeaF 本人自己寫的

侵刪

感覺不是難題。

題目中的 \(k\) 即 \(1\) 的位置在這里記作 \(m\)。

容易發現， \(a\) 序列一定是先單調遞降到 \(1\) 在單調遞增的 V 字，考慮每次彈出最前和最后，所以 \(b\) 序列在 \(1\) 之前的部分一定可以拆成兩個單調遞降的子序列，并且能拆的一定可以生成。

在 \(1\) 后面取出的方案數是顯的，其在 \(a\) 上只有兩種排列方式即單增或單降，但其是等價的，而每次只能取最前或最后，于是是 \(2 ^ {x - 1}\)（\(x\) 是剩余顏色個數）。

考慮求出 \(1\) 之前的部分，用兩個序列 \(A, B\) 表示其劃分成的子序列，并且 \(A\) 是拿 \(1\) 前一步拿的一邊，為了不重復計算我們定義一個序列的劃分是依次遍歷每個值，如果能放入 \(A\) 就放入 \(A\)，否則放入 \(B\)，容易證明其會構成雙射。

考慮計數，設 \(dp_{i,j}\) 表示當前是 \(b\) 的第 \(i\) 位，\(A\) 的最后一位是 \(j\) 的方案數，考慮轉移，分討第 \(i\) 位放到哪里了，若放到 \(A\) 則第 \(i\) 位必然填 \(j\)，且可以從 \(dp_{i - 1, k}(k>j)\) 轉移，若放到 \(B\) 則必然填剩余的最大的，若填較小的則更大的數就無處可去了（因為 \(1\) 右邊的數一定小于 \(1\) 左邊 \(B\) 中的數，而 \(B\) 又是遞降的），可以從 \(dp_{i - 1, j}\) 轉移過來。

于是方程就是：

\[dp_{i, j} = (\sum_{k = j + 1} ^ {l} dp_{i - 1, k}) + dp_{i - 1, j}= \sum_{k = j} ^ {l} dp_{i - 1, k} \]

注意到 \(k\) 的上節 \(l\)，其并不總是 \(n\)，原因是當轉移 \(dp_{i, j}\) 時，一共剩下 \(n - i\) 個元素，而 \([1, j - 1]\) 是必然剩下的，否則非法，于是 \(j - 1 \le n - i\)，即 \(l = n - i + 1\)。

上個前綴和就可以 \(\mathcal{O}(n ^ 2)\) 求了，容易想到放到格路上考慮。

先給一組固定的起點和終點，設 \(dp_{0, n + 1} = 1\)，終點是 \(\sum\limits_{i = 2}^{n - m} dp_{m - 1,i} = dp_{m, 2}\)，于是問題變成了從 \((0, n)\) 走到 \((m, 2)\)，格路形如：

將其推平，最高位是不能水平向右轉移的，加一條線表示永不碰到，于是就變成了：

直接卡特蘭數即可，一點小問題是因為最后一行的豎線存在，答案事實上求了前綴和，可以用 \((m, 2)\) 和 \((m, 3)\) 差分一下，或者直接求到 \((m - 1, 2)\) 即可。

Code


/* Local File
in_out/in.in
in_out/out.out
*/
#include <bits/stdc++.h>
using namespace std;
using llt = long long;
using ull = unsigned long long;
using llf = long double;
#define endl '\n'
#ifndef LOCAL
#undef assert
#define assert 0 &&
#define cerr 0 && cerr
FILE *InFile = freopen("game.in", "r", stdin), *OutFile = freopen("game.out", "w", stdout);
#endif

const int N = 5e5 + 3, M = N * 2 - 3;
int n, m, MOD, ans = 0;
int aas, fac[M], ivf[M];

int Fpw(int a, int b){
	if(b < 0) return 1;
	int ans = 1;
	while(b){
		if(b & 1) ans = 1ll * ans * a % MOD;
		a = 1ll * a * a % MOD, b >>= 1;
	}
	return ans;
}

int C(int a, int b){
	return a < b ? 0 : 1ll * fac[a] * ivf[b] % MOD * ivf[a - b] % MOD;
}
int P(int a, int b, int c, int d){
	int l = c - a, r = d - b;
	return C(l + r, l);
}
int Cat(int a, int b, int c, int d){
	return (1ll * P(a, d, c, b) - P(a, b - c + 2, n + 2 - d, b)) % MOD;
}

int main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	cin >> n >> m >> MOD;
	if(n == 1)
		return cout << 1, 0;
	fac[0] = 1;
	for(int i = 1; i <= M - 3; ++i)
		fac[i] = 1ll * fac[i - 1] * i % MOD;
	ivf[M - 3] = Fpw(fac[M - 3], MOD - 2);
	for(int i = M - 3; i; --i)
		ivf[i - 1] = 1ll * ivf[i] * i % MOD;
	cout << ((1ll * Cat(0, n, m, 2) - Cat(0, n, m, 3)) % MOD * Fpw(2, n - m - 1) % MOD + MOD) % MOD;
}

posted @ 2025-02-17 20:18 xrlong 閱讀(102) 評論(10) 收藏舉報

刷新頁面返回頂部

xrlong

博客密碼是 K8 色號

2025.2.17 鮮花

機關題解

公告

Loading

xrlong

博客密碼是 K8 色號

2025.2.17 鮮花

機關 題解

公告

Loading

機關題解