给定全 \(0\) 序列，第 \(i\) 次操作可以把值相同的区间的值赋值为
\(i\)，给定目标排列，求出操作方案数
有两个很明显的性质，首先，第 \(i\)
次操作区间一定包括值为 \(i\)
的位置，其次，当一个区间被操作后，这个区间与其他区间相互独立
后者是一个很好的性质，意味着对于每个区间只需要关注最小合法位置，枚举区间划分即可，最后区间相乘即可
所以，考场上写了一个 \(O(n^4)\) 的 \(DP\)
设 \(f_{p,l,r}\) 为区间 \([l,\ r]\) 第 \(p\) 次操作的操作方案数，\(g_{l,r,k}\) 为区间 \([l,\ r]\) 的不严格后继，不存在是为 \(0\)，\(q_i\) 为值为 \(i\) 的位置，则有
\[
f_{p,\ l,\ r}\ =\
\sum_{i=l}^{q_p}\sum_{j=q_p}^rf_{g_{l,i-1,p+1},l,i-1}f_{g_{i,j,p+1},i,j}f_{g_{j+1,r,p+1},j+1,r}[min_{i\le
k\le r}\lbrace s_k\rbrace\ge p]
\]
边界 \(f_{0,l,r}=1\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 1e2+5, P = 998244353;
int n, s[N], q[N];
int64 f[N][N][N];
int g[N][N][N];
int64 dp(int p, int l, int r)
{
int64 &ret = f[p][l][r];
if(ret) return ret;
if(p == 0) ret = 1;
else
{
for(int i = q[p]; i >= l&&p <= s[i]; --i)
for(int j = q[p]; j <= r&&p <= s[j]; ++j)
ret = (ret+dp(g[l][i-1][p+1], l, i-1)*dp(g[i][j][p+1], i, j)%P*dp(g[j+1][r][p+1], j+1, r)%P)%P;
}
return ret;
}
int main()
{
n = read();
for(int i = 1; i <= n; ++i) s[i] = read(), q[s[i]] = i;
for(int k = 1; k <= n; ++k)
for(int l = 1; l <= n; ++l)
for(int r = l; r <= n; ++r)
if(s[r] >= k) g[l][r][k] = min(s[r], g[l][r-1][k]?g[l][r-1][k]:n);
else g[l][r][k] = g[l][r-1][k];
printf("%lld\n", dp(1, 1, n));
return 0;
}
|
期望 \(70\) 分
实际上我们可以省略第一维状态，因为不管怎么样，\([l,\ r]\)
填的数一定是最小值，这样一个区间就确定了唯一一个对应的次序
设 \(f_{l,r}\) 为 \([l,\ r]\) 的方案数，\(g_{l,r}\) 为 \([l,\ r]\) 的最小值，不妨设为 \(x\)
则有
\[
f_{l,r}\ =\
\sum_{i=l}^{q_p}\sum_{j=q_p}^rf_{l,i-1}f_{i,q_p-1}f_{q_p+1,j}f_{j+1,r}
\]
当 \(l\ge r\) 的 \(f_{l,r}=1\)
观察上式，\(i\) 和 \(j\) 的枚举相互独立，可以优化为 \(O(n^3)\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long int64;
inline int read(int f = 1, int x = 0, char ch = ' ')
{
while(!isdigit(ch = getchar())) if(ch == '-') f = -1;
while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
return f*x;
}
const int N = 5e2+5, P = 998244353;
int n, m, p[N], q[N];
int64 f[N][N];
int g[N][N];
int64 dp(int l, int r)
{
int64 &ret = f[l][r];
if(ret) return ret;
if(l >= r) ret = 1;
else
{
int x = g[l][r];
int64 fl = 0, fr = 0;
for(int i = l; i <= q[x]; ++i) fl = (fl+dp(l, i-1)*dp(i, q[x]-1)%P)%P;
for(int i = q[x]; i <= r; ++i) fr = (fr+dp(q[x]+1, i)*dp(i+1, r)%P)%P;
ret = fl*fr%P;
}
return ret;
}
int main()
{
n = read(), m = read();
for(int i = 1; i <= n; ++i) p[i] = read(), q[p[i]] = i;
for(int l = 1; l <= n; ++l)
for(int r = l; r <= n; ++r)
g[l][r] = min(p[r], g[l][r-1]?g[l][r-1]:n);
printf("%lld\n", dp(1, n));
return 0;
}
|