妙妙 DP 题。
因为一个 $x$ 可能会对应着不同的 $p$，所以直接对 $x$ 进行计数是十分困难。所以我们尝试对于特定的 $p$ 与 $x$ 建立双射关系。我们尝试用 $x$ 来构造 $p$。
假设已知 $x$，求一个对应的 $p$。我们从大到小考虑每个数。若剩下的经过 $i$ 的区间都有 $x=i$ ，我们称 $i$ 为可行位置。我们每次将当前 $n$ 放在最靠左的一个可行位置上，然后删去所有经过 $i$ 的区间。一直的重复直到区间删完。但是，这样可能存在一些位置没有被选到。于是为了确定唯一的 $p$，我们加入新的 $n$ 个区间 $[i,i],i\in [1,n]$。
显然这样生成的排列 $p$ 与 $x$ 构成双射关系。并且 $x$ 当且仅当可以生成 $p$ 时合法。问题转化为对排列 $p$ 的计数。
观察限制条件：在删去经过该点的区间后，左右两侧的区间之间是相互独立的。对于右侧区间是没有影响的，但是对于左侧区间有影响。经过该点的区间中必然存在一个区间包含当前最大值与左边的最大值。证明很简单，如果没有这样的区间的话，我们直接选择左侧的区间即可，当前情况就不合法了。所以说我们需要限制左侧区间的 $x$ 大于 经过该点的区间的最左端点。
于是 DP 就很显然了。设计 $f(l,r,k)$ 表示 $[l,r]$ 的 $x\ge k$ 的方案数，容易得到转移方程：
其中 $pos_{l,r,k}$ 为在 $[l,r]$ 之内的区间且包含 $k$ 的最左端点。
Code
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
41
42
43
44
45
46
47
48
| #include<iostream>
#include<cstdio>
using namespace std;
const int N=300+10,mod=998244353;
template<class T>
inline void read(T &x)
{
x=0;int f=0;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
read(x),read(x1...);
}
int n,m;
int pos[N][N][N],f[N][N][N];
inline int adj(int x){return (x>=mod)?x-mod:x;}
int main()
{
read(n,m);
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
for(int k=1;k<=n;k++)
pos[i][j][k]=n+1;
for(int i=1;i<=m;i++)
{
int l,r;
read(l,r);
for(int j=l;j<=r;j++)pos[l][r][j]=min(pos[l][r][j],l);
}
for(int i=n-1;i;i--)
for(int j=i+1;j<=n;j++)
for(int k=i;k<=j;k++)
pos[i][j][k]=min(pos[i][j][k],min(pos[i+1][j][k],pos[i][j-1][k]));
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n+1;j++)
f[i][i-1][j]=1;
for(int i=n;i;i--)
for(int j=i;j<=n;j++)
for(int k=j;k>=i;k--)
f[i][j][k]=adj(f[i][j][k+1]+1ll*f[i][k-1][pos[i][j][k]]*f[k+1][j][k+1]%mod);
printf("%d\n",f[1][n][1]);
return 0;
}
|