题意
求有多少种长度为 \(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;
}
`
标签:20230324,include,省选,T3,tp,int,1ll,Mod,mod
From: https://www.cnblogs.com/cxqghzj/p/18080430