题解：CF1988F Heartbeat

· · 题解

更好的阅读体验

这道题怎么这么像随机字符串，真恶心。

首先有一个观察，就是考虑全局最大值位置 p，那么 [1, p) 只有前缀最大值，(p, n] 只有后缀最大值。这启发我们分开计算。

假设 f_{i, j, k} 表示 i 个数的排列，j 个前缀最大值，k 个上升位的方案数。参考 P9197 [JOI Open 2016] 摩天大楼 / Skyscraper，进行插入 dp，每次插入一个最小值。

  1. 插最左边，上升位和前缀最大值都 +1，方案数为 f_{i-1, j-1, k-1}。
  2. 插最右边，上升位和前缀最大值都不变，方案数为 f_{i-1, j, k}。
  3. 插两个上升的数字之间。上升位和前缀最大值数量都不变，方案数为 k \cdot f_{i-1, j, k}。
  4. 插在两个下降的数字之间，上升位 +1，前缀最大值数量不变，方案数为 (i - k - 1) \cdot f_{i-1, j, k-1}。

如上转移 f_{i, j, k}。

我们相似地，令 g_{i, j, k} 表示 i 个数，j 个后缀最大值，k 个上升位的方案数。转移同上。

那么我们假设排列长度为 n 时答案为 S_n。那么

S_n = \sum_{p = 1}^n \sum_{i = 0}^{p-1} \sum_{j = 0}^{n-p} \sum_{x = 0}^{p-1}\sum_{y = 0}^{n-p} {n-1 \choose p-1}f_{p-1,i,x} g_{n-p,j,y}a_{i+1}b_{j+1}c_{x+y+[p>1]}

解释一下这个式子。p 是 n 的位置，i, j, x, y 分别表示：左边有几个前缀最大值，右边有多少个后缀最大值，左边有几个上升位，右边有几个上升位。n-1 \choose p-1 表示左右两边的数字是独立的，要从剩下 n-1 个数字中选 p-1 个放到左边，其他放到右边。

调换求和顺序。假设

u_{n, x} = \sum_{i = 0}^nf_{n, i, x}a_{i+1}, v_{n, x} = \sum_{j = 0}^ng_{n, j, y}b_{j+1} S_n = \sum_{p=1}^n \sum_{x=0}^{p-1} \sum_{y=0}^{n-p}{n-1 \choose p-1}u_{p-1,x}v_{n-p,y}c_{x+y+[p>1]}

拆掉组合数，假设

i = p-1, j = n-p S'_n = \frac{S_n}{(n-1)!}, u'_{n, x} = \frac{u_{n,x}}{n!}, v'_{n, x} = \frac{v_{n,x}}{n!} S'_{i + j + 1} \leftarrow \sum_{x = 0}^i \sum _{y = 0}^j u'_{i, x}v'_{j, y}c_{x+y+[i > 0]} = \sum_{y = 0}^j v'_{j, y} \sum_{x = 0}^iu'_{i, x}c_{x+y+[i>0]}

我们可以对于每个 i, y 预处理

s_{i, y} = \sum_{x = 0}^iu'_{i, x}c_{x+y+[i>0]} S'_{i + j + 1} \leftarrow \sum_{y=0}^j v'_{j, y} s_{i, y}

我们枚举 i, j, y，不难做到 O(n^3)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 706
#define MOD 998244353
using namespace std;
inline void add(int &x,int y){x+=y,x-=x>=MOD?MOD:0;}
int n,a[N],b[N],c[N],fac[N],ifac[N];
int f[2][N][N],g[2][N][N],u[N][N],v[N][N],s[N][N],ans[N];
int qpow(int x,int y=MOD-2)
{
    int ret=1;
    for(;y;x=1ll*x*x%MOD,y>>=1)if(y&1)ret=1ll*ret*x%MOD;
    return ret;
}
void init()
{
    fac[0]=1;
    for(int i=1;i<N;i++)fac[i]=1ll*i*fac[i-1]%MOD;
    ifac[N-1]=qpow(fac[N-1]);
    for(int i=N-2;~i;i--)ifac[i]=1ll*ifac[i+1]*(i+1)%MOD;
}
int binom(int x,int y){return x<y?0:1ll*fac[x]*ifac[y]%MOD*ifac[x-y]%MOD;}
main()
{
    scanf("%d",&n),init();
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)scanf("%d",&b[i]);
    for(int i=0;i<n;i++)scanf("%d",&c[i]);
    f[1][1][0]=1,u[0][0]=a[1],u[1][0]=a[2];
    for(int i=2,cur;i<=n;i++)
    {
        cur=i&1,memset(f[cur],0,sizeof(f[cur]));
        for(int j=0;j<=i;j++)
            for(int k=0;k<=i;k++)
            {
                if(j&&k)add(f[cur][j][k],f[cur^1][j-1][k-1]);
                add(f[cur][j][k],f[cur^1][j][k]);
                add(f[cur][j][k],1ll*f[cur^1][j][k]*k%MOD);
                if(k)add(f[cur][j][k],1ll*f[cur^1][j][k-1]*(i-k-1+MOD)%MOD);
            }
        for(int j=0;j<=i;j++)
        {
            for(int k=0;k<=i;k++)add(u[i][j],1ll*f[cur][k][j]*a[k+1]%MOD);
            u[i][j]=1ll*u[i][j]*ifac[i]%MOD;
        }
    }
    g[1][1][0]=1,v[0][0]=b[1],v[1][0]=b[2];
    for(int i=2,cur;i<=n;i++)
    {
        cur=i&1,memset(g[cur],0,sizeof(g[cur]));
        for(int j=0;j<=i;j++)
            for(int k=0;k<=i;k++)
            {
                if(j)add(g[cur][j][k],g[cur^1][j-1][k]);
                if(k)add(g[cur][j][k],g[cur^1][j][k-1]);
                add(g[cur][j][k],1ll*g[cur^1][j][k]*k%MOD);
                if(j)add(g[cur][j][k],1ll*g[cur^1][j][k-1]*(i-1-k+MOD)%MOD);
            }
        for(int j=0;j<=i;j++)
        {
            for(int k=0;k<=i;k++)add(v[i][j],1ll*g[cur][k][j]*b[k+1]%MOD);
            v[i][j]=1ll*v[i][j]*ifac[i]%MOD;
        }
    }
    for(int i=0;i<n;i++)
        for(int y=0;y<=n;y++)
            for(int x=0;x+y+(i>0)<n&&x<=i;x++)add(s[i][y],1ll*u[i][x]*c[x+y+(i>0)]%MOD);
    for(int i=0;i<n;i++)
        for(int j=0;i+j<n;j++)
            for(int y=0;y<=j;y++)add(ans[i+j+1],1ll*v[j][y]*s[i][y]%MOD);
    for(int i=1;i<=n;i++)
        printf("%lld%c",1ll*ans[i]*fac[i-1]%MOD," \n"[i==n]);
    return 0;
}