My Blogs
CF1988F Heartbeat
最大值把序列分成两部分，前一部分对前缀最大值个数有贡献，后一部分对后缀最大值个数有贡献，可以分开算。
设 $f_{i,j,k}$ 表示 $[1,i]$ 的排列，有 $j$ 个前缀最大值，$k$ 个上升的位置的方案数。不断向右边加数不好做，不断加入 $n+1$ 也不好做，因为可能前缀最大值个数会变少。所以考虑不断的加入新的 $1$，把原来的值域整体平移。转移比较平凡：
- $1$ 放在最前面：$f_{i+1,j+1,k+1}\leftarrow f_{i,j,k}$。
- $1$ 放在最后面：$f_{i+1,j,k}\leftarrow f_{i,j,k}$。
- $1$ 放在上升的位置中间：$f_{i+1,j,k}\leftarrow f_{i,j,k}\times j$。
- $1$ 放在下降的位置中间：$f_{i+1,j+1,k}\leftarrow f_{i,j,k}\times (i-1-j)$。
预处理这部分的复杂度是 $\mathcal O(n^3)$ 的。
接下来考虑把两个拼起来。因为前缀最大值个数和后缀最大值个数是独立的，所以可以先把 $A,B$ 序列的权值直接乘进去。一个上升位置为 $j$ 的长度为 $i$ 的序列显然有 $i-1-j$ 个下降位置。所以前缀的方案数把 $k$ 全部变成 $i-1-k$ 就是后缀的方案数。
处理出 $l_{i,j}$ 表示长度为 $i$ 的序列有 $j$ 个上升位，统计前缀最大值个数的贡献。$r_{i,j}$ 表示长度为 $i$ 的序列有 $j$ 个上升位，统计后缀最大值个数的贡献：
\[\begin{aligned} l_{i,k}&=\sum_{j=1}^i f_{i,j,k}\times a_j\\ r_{i,i-1-k}&=\sum_{j=1}^i f_{i,j,k}\times b_j \end{aligned}\]接下来只需要统计上升位 $C$ 序列的贡献。设 $ans_{i,j}$ 表示长度为 $i$ 的序列有 $j$ 个上升位，统计了前后缀最大值个数的贡献和。朴素的拼起来：
\[ans_{i+j+1,k+o+1}\leftarrow l_{i,k}\times r_{j,o}\times \binom{i+j}{i}\]$ans$ 的两个下标都 $+1$ 是因为强制要求最大值在中间。暴力做复杂度是 $\mathcal O(n^4)$。
如何优化？首先变形一下式子。
\[\frac{ans_{i+j+1,k+o+1}}{(i+j)!}\leftarrow \frac{l_{i,k}}{i!}\times \frac{r_{j,o}}{j!}\]发现转移是二维卷积的形式，可以用拉插优化。首先设 $L_i(x)=\sum_{j=0}^{i-1}l_{i,j}x^j,R_i(x)=\sum_{j=0}^{i-1}r_{i,j}x^j$。注意这里的 $l,r$ 都要除一个阶乘，设 $Ans_i(x)=\sum_{j=0}^{i-1}ans_{i,j}x^j$，则：
\[Ans_{i+j}(x)\leftarrow L_i(x)R_j(x)\]相乘指多项式乘法，加法指对应系数相加。$Ans(x)$ 是 $n-1$ 次多项式，可以先求出 $L(x),R(x)$ 在 $x\in [1,n]$ 处 $n$ 个地方的点值，设其为 $L’_i(x),R’_i(x)$，然后 $Ans(x)$ 的点值就是对应位相乘再相加：
\[Ans'_{i+j}(x)=L'_i(x)R'_i(x)\]相乘指对应位置相乘，相加指对应位置相加。这样求出 $Ans_i$ 的 $n$ 处点值，再用拉插把真实的多项式插出来，这样系数就是做二维卷积的结果。求点值复杂度 $\mathcal O(n^3)$，相乘复杂度 $\mathcal O(n^3)$，拉插求系数复杂度 $\mathcal 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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
int a[710],b[710],c[710],A[710],B[710][710];
int n,now,pre,f[2][710][710],l[710][710],r[710][710];
int vl[710],vr[710],x[710][710],d[710];
int fr[710],inv[710];
inline int C(int n,int m){return m<0||m>n?0:Cmul(fr[n],inv[m],inv[n-m]);}
inline void mian()
{
read(n),f[1][0][1]=1,fr[0]=inv[0]=1;
for(int i=1;i<=n;++i)fr[i]=Cmul(fr[i-1],i);
inv[n]=power(fr[n],MOD-2);
for(int i=n-1;i>0;--i)inv[i]=Cmul(inv[i+1],i+1);
for(int i=1;i<=n;++i)read(a[i]);
for(int i=1;i<=n;++i)read(b[i]);
for(int i=0;i<n;++i)read(c[i]);
l[1][0]=a[1],r[1][0]=b[1];
l[2][1]=a[2],r[2][0]=b[2];
now=1,pre=0;
for(int i=1;i<n;++i)
{
swap(pre,now),memset(f[now],0,sizeof(f[now]));
for(int j=0;j<i;++j)
{
for(int k=1;k<=i;++k)
{
Madd(f[now][j+1][k+1],f[pre][j][k]);//1 placed in front
Madd(f[now][j][k],f[pre][j][k]);//1 placed in end
Madd(f[now][j][k],Cmul(j,f[pre][j][k]));//1 placed between a up
Madd(f[now][j+1][k],Cmul(i-1-j,f[pre][j][k]));//1 placed between a down
}
}
for(int j=0;j<i+1;++j)for(int k=1;k<=i+1;++k)
Madd(l[i+2][j+1],Cmul(f[now][j][k],a[k+1])),
Madd(r[i+2][i-j],Cmul(f[now][j][k],b[k+1]));
}
for(int i=1;i<=n;++i)for(int j=0;j<i;++j)Mmul(l[i][j],inv[i-1]);
for(int i=1;i<=n;++i)for(int j=0;j<i;++j)Mmul(r[i][j],inv[i-1]);
for(int X=1;X<=n+2;++X)
{
for(int i=1;i<=n;++i)
{
int v=0;
for(int j=0,s=1;j<i;++j,s=Cmul(s,X))
Madd(v,Cmul(s,l[i][j]));
vl[i]=v,v=0;
for(int j=0,s=1;j<i;++j,s=Cmul(s,X))
Madd(v,Cmul(s,r[i][j]));
vr[i]=v;
}
for(int i=1;i<=n;++i)
{
for(int j=1;j+i-1<=n;++j)
Madd(x[i+j-1][X],Cmul(vl[i],vr[j]));
}
}
A[0]=1;
for(int i=1;i<=n+2;++i)
{
for(int j=i;j>=1;--j)A[j]=Cdel(A[j-1],Cmul(i,A[j]));
Mmul(A[0],MOD-i);
}
for(int j=1;j<=n+2;++j)
{
int c=power(MOD-j,MOD-2);B[j][0]=Cmul(A[0],c);
for(int k=1;k<=n+1;++k)B[j][k]=Cmul(Cdel(A[k],B[j][k-1]),c);
}
for(int i=1;i<=n;++i)
{
memset(d,0,sizeof(d));
for(int j=1,v;j<=n+2;++j)
{
v=1;
for(int k=1;k<=n+2;++k)if(j!=k)Mmul(v,Cdel(j,k));
v=Cmul(x[i][j],power(v,MOD-2));
for(int k=0;k<=n;++k)Madd(d[k],Cmul(v,B[j][k]));
}
int ans=0;
for(int j=0;j<n;++j)Madd(ans,Cmul(d[j],c[j]));
write(Cmul(ans,fr[i-1]));
}
}