My Blogs
P10008 [集训队互测 2022] Range Minimum Element
难点在于双射构造。
首先考虑给定了 $b$ 如何进行判定。从小到大填数 $x$，每次把能填的地方（$b_i>x$ 的区间之外）全部填上 $x$，这样填一定是最优的。合法当且仅当这样生成的序列 $a$ 对应的 $b$ 就是 $b$ 本身。
发现通过这样的生成方式，合法的 $a$ 和 $b$ 是一一对应的，所以对 $b$ 计数可以转为对能被这样生成的 $a$ 计数。
如果给定了 $a$，如何判 $a$ 是否合法？找到第一个最小值的位置 $p$，把 $A[1,n]$ 变成 $A[1,p-1]$ 和 $A[p+1,n]$。因为 $[1,p-1]$ 中并没有被填上最小值，所以被 $[1,p-1]$ 包含的区间一定选择的都是大于最小值的数，并且他们的的并集一定是 $[1,p-1]$。然后递归判断 $A[1,p-1]$ 和 $A[p+1,n]$ 是否合法。
上述过程是值域从小到大，分裂序列。计数就考虑值域从大到小，合并序列。$f_{l,r,x}$ 表示区间 $[l,r]$ 填入了 $[x,c]$ 中的数的方案数。转移就是枚举最小值的位置 $p$：
\[\begin{aligned} f_{l,r,x}&\leftarrow [[l,r]\mathrm{合法}]\times f_{l,r,x+1}\\ f_{l,r,x}&\leftarrow [[l,p-1]\mathrm{合法}]\times f_{l,p-1,x+1}\times f_{p+1,r,x} \end{aligned}\]第一种转移表示区间内没有 $=x$ 的数。预处理合法区间，暴力做复杂度是 $\mathcal O(n^3c)$。套路性的，不难归纳证明 $f_{l,r,x}$ 是一个关于 $x$ 的 $\mathcal O(r-l)$ 次多项式。
令 $x\leftarrow c-x+1$，这样可以暴力求得 $f_{1,n,1\sim n+1}$，然后可以拉插出 $x=c$ 的点值，复杂度是 $\mathcal O(m+n^4)$。
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
int n,m,K,f[110][110][110];
bool v[110][110];
inline void mian()
{
read(n,m,K);int x,y,ans=0;
while(m--)read(x,y),v[x][y]=1;
for(int i=n;i>=1;--i)
{
for(int j=i;j<=n;++j)
{
int x=-1,y=-1;
for(int k=j;k>=i;--k)if(v[i][k]){x=k;break;}
for(int k=i;k<=j;++k)if(v[k][j]){y=k;break;}
if(x==-1||y==-1)continue;
v[i][j]|=x>=y-1;
}
}
for(int i=1;i<=n;++i)v[i][i-1]=1;
for(int i=1;i<=n;++i)for(int j=i;j<=n;++j)f[1][i][j]=1;
for(int i=1;i<=n+1;++i)for(int j=1;j<=n+1;++j)f[i][j][j-1]=1;
for(int x=2;x<=n+1;++x)
{
for(int i=n;i>=1;--i)
{
for(int j=i;j<=n;++j)
{
if(v[i][j])f[x][i][j]=f[x-1][i][j];
for(int k=i;k<=j;++k)if(v[i][k-1])
Madd(f[x][i][j],Cmul(f[x-1][i][k-1],f[x][k+1][j]));
}
}
}
for(int i=1;i<=n+1;++i)
{
int v=1,x=1;
for(int j=1;j<=n+1;++j)if(i!=j)Mmul(v,Cdel(i,j)),Mmul(x,Cdel(K,j));
Madd(ans,Cmul(x,power(v,MOD-2),f[i][1][n]));
}
write(ans);
}