我们考虑给定 \(X\),如何贪心地求 \(f(X)\)。
- 队列为空时加入队首或队尾都是一样的。
- 队列不为空,设队首为 \(c\)。因为我们的目标是最小化字典序,于是如果 \(X_i \le c\),我们把 \(X_i\) 加入队首,否则加入队尾。由此也容易发现,加入队首的数一定单调不升。
考虑到既可以在头部加数也可以在尾部加数,套路地考虑区间 dp。设 \(f_{l, r}\) 为 \(Y_{l \sim r}\) 对应的 \(X\) 个数。设 \(n = |Y|\),初值 \(\forall i \in [1, n], f_{i, i} = 1\)。有转移:
答案为 \(f_{1, n}\)。
至此可做到 \(O(n^2)\)。
考虑一些神奇的事情。我们对于 \((l, r)\) 建出网格图,若 \((l, r)\) 可转移到 \((l - 1, r)\) 或 \((l, r + 1)\) 就在二者之间连边。例如对于 \(Y = \texttt{12234433442}\) 我们可以得到以下的网格图:
现在问题转化成了求这张网格图上,\(\forall i \in [1, n], (i, i) \to (1, n)\) 的路径个数之和。
观察这张图,发现很多点和边是多余的。考虑删除它们。设 \(Y_{1 \sim p}\) 是极长不降子段,那我们仅保留 \(l \le p\) 的点。对于一个 \(l\),它延伸出去的 \(r\) 满足 \([l, r]\) 中除与 \(l\) 在同一个同色连续段的点后不存在 \(Y_i \le Y_l\)。并且与 \(l\) 在同一个同色连续段的非右端点的点没有向右的转移。
简化后的网格图长这样:
考虑倒序枚举 \(l\),动态维护 \(f_{l, r}\)。对于一个同色连续段的 \(l\) 合并考虑。设连续段长度为 \(k\),你每次要做这样的事情:
- 在 \(f_l\) 前添加 \(k\) 个 \(1\);
- 做 \(k\) 遍从连续段右端点到 \(R\) 的前缀和,其中 \(R\) 为 \(f_{l, r}\) 有效的最大的 \(r\)。
求序列 \(a_{1 \sim n}\) 的 \(k\) 阶前缀和容易使用 NTT 优化至 \(O(n \log n)\),这里简单讲一下。设 \(b_i\) 为 \(k\) 阶前缀和后的序列。考虑 \(a_j\) 对 \(b_i\) 的贡献系数。不难发现每次前缀和时 \(j\) 可以贡献到 \(\ge j\) 的所有位置。贡献系数也就是满足 \(p_0 = j \le p_1 \le p_2 \le \cdots \le p_m = i\) 的 \(p\) 序列个数。容易插板法得到贡献系数为 \(\binom{i - j + k - 1}{k - 1}\)。于是我们有 \(b_i = \sum\limits_{j = 1}^i a_j \times \binom{i - j + k - 1}{k - 1}\),这是显然的加法卷积形式,NTT 优化即可。
因为有效的 \(l\),\(Y_l\) 单调不降,所以同色连续段个数是 \(O(|\Sigma|)\) 的。因此最后的时间复杂度就是 \(O(|\Sigma| n \log n)\)。
code
// Problem: E - Deque Minimization
// Contest: AtCoder - AtCoder Regular Contest 153
// URL: https://atcoder.jp/contests/arc153/tasks/arc153_e
// Memory Limit: 1024 MB
// Time Limit: 5000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
/*
考虑先写出区间 dp 转移式子。
考虑有转移则连边,抽象到在网格图上走,从主对角线到 $(1, n)$ 方案数。
删除无用转移,转化为 $|\Sigma|$ 次在开头加入若干个 $1$,做若干次前缀和。次数取决于段的长度。
NTT 优化即可。
*/
const int maxn = 1000100;
const int N = 1000000;
const ll mod = 998244353, G = 3;
inline ll qpow(ll b, ll p) {
ll res = 1;
while (p) {
if (p & 1) {
res = res * b % mod;
}
b = b * b % mod;
p >>= 1;
}
return res;
}
ll n, fac[maxn], ifac[maxn], f[maxn], g[maxn];
char s[maxn];
struct node {
int l, r, x;
node(int a = 0, int b = 0, int c = 0) : l(a), r(b), x(c) {}
} a[maxn];
inline void init() {
fac[0] = 1;
for (int i = 1; i <= N; ++i) {
fac[i] = fac[i - 1] * i % mod;
}
ifac[N] = qpow(fac[N], mod - 2);
for (int i = N - 1; ~i; --i) {
ifac[i] = ifac[i + 1] * (i + 1) % mod;
}
}
inline ll C(ll n, ll m) {
if (n < m || n < 0 || m < 0) {
return 0;
} else {
return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
}
}
int r[maxn];
typedef vector<ll> poly;
inline poly NTT(poly a, int op) {
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
if (i < r[i]) {
swap(a[i], a[r[i]]);
}
}
for (int k = 1; k < n; k <<= 1) {
ll wn = qpow(op == 1 ? G : qpow(G, mod - 2), (mod - 1) / (k << 1));
for (int i = 0; i < n; i += (k << 1)) {
ll w = 1;
for (int j = 0; j < k; ++j, w = w * wn % mod) {
ll x = a[i + j], y = w * a[i + j + k] % mod;
a[i + j] = (x + y) % mod;
a[i + j + k] = (x - y + mod) % mod;
}
}
}
if (op == -1) {
ll inv = qpow(n, mod - 2);
for (int i = 0; i < n; ++i) {
a[i] = a[i] * inv % mod;
}
}
return a;
}
inline poly operator * (poly a, poly b) {
a = NTT(a, 1);
b = NTT(b, 1);
int n = (int)a.size();
for (int i = 0; i < n; ++i) {
a[i] = a[i] * b[i] % mod;
}
a = NTT(a, -1);
return a;
}
inline void calc(int l, int r, int t) {
int n = r - l, k = 0;
while ((1 << k) <= (n + 1) * 2) {
++k;
}
for (int i = 1; i < (1 << k); ++i) {
::r[i] = (::r[i >> 1] >> 1) | ((i & 1) << (k - 1));
}
poly A(1 << k), B(1 << k);
for (int i = 0; i <= n; ++i) {
A[i] = f[l + i];
B[i] = C(i + t - 1, t - 1);
}
poly res = A * B;
for (int i = 0; i <= n; ++i) {
f[l + i] = res[i];
}
}
void solve() {
scanf("%s", s + 1);
n = strlen(s + 1);
int m = 0;
for (int i = 1, j = 1; i <= n; i = (++j)) {
while (j < n && s[j + 1] == s[i]) {
++j;
}
if (m && s[i] - '0' < a[m].x) {
break;
}
a[++m] = node(i, j, s[i] - '0');
}
for (int i = m; i; --i) {
int j = a[i].r;
while (j < n && s[j + 1] - '0' > a[i].x) {
++j;
}
for (int k = a[i].l; k <= a[i].r; ++k) {
f[k] = 1;
}
calc(a[i].r, j, a[i].r - a[i].l + 1);
}
printf("%lld\n", f[n]);
}
int main() {
init();
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
启发:对于 \(f_{l, r}\) 只能贡献到 \(f_{l + 1, r}\) 和 \(f_{l, r - 1}\) 的 区间 dp,考虑建出网格图,去除无用点和边后可能可以做到更优。
- Minimization AtCoder Regular Contest Dequeminimization atcoder regular contest atcoder regular contest deque atcoder regular contest 165 atcoder regular contest 166 atcoder regular contest 167 atcoder regular contest sliding atcoder regular contest degree atcoder regular contest 164 atcoder regular contest builder subsegments atcoder regular contest