LY1165 [ 20230324 CQYC省选模拟赛 T3 ] 迷雾

题意

求有多少种长度为 \(N\) 的满足以下条件的序列。

• 是一个 \(1 \sim N\) 的排列。
• 至少 进行 \(K\) 次操作后，该序列才含有一个元素。

\(N \le 1000\)

Sol

首先因为序列是一个排列，所以操作次数不会太多。

操作次数大概在 \(\log N\) 的级别。

不难注意到对于一个数列，剩下的只会是 \(N\)。

考虑枚举 \(N\) 所在的位置，发现左右两边的贡献互不影响。

动态规划。设 \(f_{i, j, 0 / 1 / 2}\) 表示当前排列的长度为 \(i\)，操作 \(j\) 次后清空 或 只剩下 \(N\)（在无法清空的情况下）。\(0 / 1 / 2\) 分别表示当前序列两边都没有限制、有一边为 \(\infty\)、两边都为 \(\infty\)。

对于当前的状态，枚举 \(N\) 的位置，不难发现左右两边需要有一边顶满操作 \(j\) 次的限制。

直接跑一遍 dp 即可。

复杂度：\(O(n ^ 2 \log n)\)。

Code

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define ll long long
#define il inline
using namespace std;
#ifdef ONLINE_JUDGE

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;

#endif
il int read() {
	int p = 0, flg = 1;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') flg = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		p = p * 10 + c - '0';
		c = getchar();
	}
	return p * flg;
}
void write(int x) {
	if (x < 0) {
		x = -x;
		putchar('-');
	}
	if (x > 9) {
		write(x / 10);
	}
	putchar(x % 10 + '0');
}
bool _stmer;

const int N = 1e3 + 5, M = 21;

array <array <array <int, 3>, M>, N> f, g;

int pow_(int x, int k, int p) {
	int ans = 1;
	while (k) {
		if (k & 1) ans = 1ll * ans * x % p;
		x = 1ll * x * x % p;
		k >>= 1;
	}
	return ans;
}

int mod;

array <int, N> fac, inv;

il void init(int n) {
	fac[0] = 1;
	for (int i = 1; i <= n; i++)
		fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[n] = pow_(fac[n], mod - 2, mod);
	for (int i = n; i; i--)
		inv[i - 1] = 1ll * inv[i] * i % mod;
}

il int C(int n, int m) {
	if (n < m) return 0;
	return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}

il void Mod(int &x) {
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

bool _edmer;
signed main() {
	cerr << (&_stmer - &_edmer) / 1024.0 / 1024.0 << "MB\n";
#ifndef cxqghzj
	freopen("misty.in", "r", stdin);
	freopen("misty.out", "w", stdout);
#endif
	int n = read(), k = read(), p = read();
	::mod = p, init(1000);
	if (k > 12) return puts("0"), 0;
	f[0][0][0] = f[0][0][1] = f[0][0][2] = 1, g = f;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= 12; j++)
			for (int p = 0; p <= 2; p++)
				g[i - 1][j][p] = g[i - 1][j - 1][p] + f[i - 1][j][p], Mod(g[i - 1][j][p]);
		/* if (i == 2) */
			/* write(g[1][1][1]), puts(""); */
		for (int j = 1; j <= 12; j++) {
			for (int k = 1; k <= i; k++) {
				int tp = 0;
				tp += (1ll * f[k - 1][j][1] * g[i - k][j][1] % mod), Mod(tp);
				tp += (1ll * f[i - k][j][1] * g[k - 1][j - 1][1] % mod), Mod(tp);
				f[i][j][0] += 1ll * tp * C(i - 1, k - 1) % mod, Mod(f[i][j][0]);

				tp = 0;
				tp += (1ll * f[k - 1][j - 1][2] * g[i - k][j][1] % mod), Mod(tp);
				/* if (i == 2 && j == 1) */
					/* write(g[i - k][j][1]), puts("@"); */
				if (j > 1)
					tp += (1ll * f[i - k][j][1] * g[k - 1][j - 2][2] % mod), Mod(tp);
				f[i][j][1] += 1ll * tp * C(i - 1, k - 1) % mod, Mod(f[i][j][1]);

				tp = 0;
				tp += (1ll * f[k - 1][j][2] * g[i - k][j - 1][2] % mod), Mod(tp);
				tp += (1ll * f[i - k][j][2] * g[k - 1][j - 1][2] % mod), Mod(tp);
				tp += (1ll * f[k - 1][j - 1][2] * f[i - k][j - 1][2] % mod), Mod(tp);
				f[i][j][2] += 1ll * tp * C(i - 1, k - 1) % mod, Mod(f[i][j][2]);
			}
		}
	}
	/* for (int i = 0; i <= n; i++) */
		/* for (int j = 0; j <= 20; j++) */
			/* write(f[i][j][1]), putchar(" \n"[j == 20]); */
	int ans = 0;
	for (int i = k; i <= 12; i++)
		ans += f[n][i][0], Mod(ans);
	write(ans), puts("");
	return 0;
}
`