题解：CF1988F Heartbeat

Arghariza · 2024-07-16 16:38:54 · 题解

复读官方题解。

设 f_{n,i,j} 为长为 n 的有 i 个前缀最大值 j 个上升的排列个数，g_{n,i,j} 为长为 n 的有 i 个后缀最大值 j 个上升的排列个数（n\ge 2）。考虑类似欧拉数的转移，即最小值插入在哪个位置，以 f_{n,i,j} 为例（g_{n,i,j} 同理）：

放在首位，f_{n,i,j}\gets f_{n-1,i-1,j-1}。
放在末尾，f_{n,i,j}\gets f_{n-1,i,j}。
放在上升的两个数之间，f_{n,i,j}\gets f_{n-1,i,j}\cdot j。
放在下降的两个数之间，f_{n,i,j}\gets f_{n-1,i,j-1}(n-j-1)。

即得：

f_{n,i,j}=f_{n-1,i-1,j-1}+f_{n-1,i,j}(j+1)+f_{n-1,i,j-1}(n-j-1)

g_{n,i,j}=g_{n-1,i-1,j}+g_{n-1,i,j}\cdot j+g_{n-1,i,j-1}(n-j)

对于长度为 n 的排列，考虑枚举最大值的位置 p 以及最大值两边怎么填，答案就是：

\begin{aligned}S_n&=\sum\limits_{p=1}^n\sum\limits_{i=0}^{p-1}\sum\limits_{j=0}^{n-p}\sum\limits_{x=0}^{p-1}\sum\limits_{y=0}^{n-p}\dbinom{n-1}{p-1}f_{p-1,i,x}g_{n-p,j,y}a_{i+1}b_{j+1}c_{x+y+[p>1]}\\&=\sum\limits_{p=1}^n\dbinom{n-1}{p-1}\sum\limits_{x=0}^{p-1}\left(\sum\limits_{i=0}^{p-1}f_{p-1,i,x}a_{i+1}\right)\sum\limits_{y=0}^{n-p}\left(\sum\limits_{j=0}^{n-p}g_{n-p,j,y}b_{j+1}\right)c_{x+y+[p>1]}\end{aligned}

令 u_{n,x}=\sum\limits_{i=0}^nf_{n,i,x}a_{i+1}，v_{n,y}=\sum\limits_{j=0}^ng_{n,j,y}a_{j+1}：

S_n=\sum\limits_{p=1}^n\sum\limits_{x=0}^{p-1}\sum\limits_{y=0}^{n-p}\dbinom{n-1}{p-1}u_{p-1,x}v_{n-p,y}c_{x+y+[p>1]}

考虑枚举 i=p-1,j=n-p,0\le x\le i,0\le y\le j，将 \dbinom{i+j}{i}u_{i,x}v_{j,y}c_{x+y+[i\neq 0]} 贡献到 S_{i+j+1} 处：

\begin{aligned}S_{i+j+1}&\gets \sum\limits_{x=0}^i\sum\limits_{y=0}^j\dbinom{i+j}{i}u_{i,x}v_{j,y}c_{x+y+[i\neq 0]}\\&\gets \sum\limits_{x=0}^i\sum\limits_{y=0}^j\frac{u_{i,x}}{i!}\cdot \frac{v_{j,y}}{j!}\cdot (i+j)!c_{x+y+[i\neq 0]}\end{aligned}

令 S'_n=\frac{S_n}{(n-1)!}，u'_{i,x}=\frac{u_{i,x}}{i!}，v'_{j,y}=\frac{v_{j,y}}{j!}：

\begin{aligned}S'_{i+j+1}&\gets \sum\limits_{x=0}^i\sum\limits_{y=0}^ju'_{i,x}v'_{j,y}c_{x+y+[i\neq 0]}\end{aligned}

再令 s_{i,y}=\sum\limits_{x=0}^iu'_{i,x}c_{x+y+[i\neq 0]}，则只需枚举 i,j,y 贡献：

S'_{i+j+1}\gets \sum\limits_{y=0}^jv'_{j,y}s_{i,y}

以上时间复杂度均为 O(n^3)，做完了。

注意对边界情况的处理。

// Problem: F. Heartbeat
// Contest: Codeforces - Codeforces Round 958 (Div. 2)
// URL: https://codeforces.com/problemset/problem/1988/F
// Memory Limit: 512 MB
// Time Limit: 5000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
#define eb emplace_back
#define mt make_tuple
#define mp make_pair
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
bool Mbe;

const int N = 705;
const int P = 998244353;

int n, a[N], b[N], c[N], fc[N], ifc[N];
int f[10][N][N], g[10][N][N], u[N][N], v[N][N], s[N][N], ans[N];

void Add(int &x, int y) { x += y, (x >= P) && (x -= P); }
int qpow(int p, int q) {
    int res = 1;
    for (; q; q >>= 1, p = 1ll * p * p % P)
        if (q & 1) res = 1ll * res * p % P;
    return res;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 0; i < n; i++) cin >> c[i];
    fc[0] = 1; for (int i = 1; i <= n; i++) fc[i] = 1ll * fc[i - 1] * i % P;
    ifc[n] = qpow(fc[n], P - 2); for (int i = n - 1; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % P;
    f[1][1][0] = g[1][1][0] = 1, u[0][0] = a[1], u[1][0] = a[2], v[0][0] = b[1], v[1][0] = b[2];
    for (int i = 2, op = 0; i <= n; i++, op ^= 1) {
        memset(f[op], 0, sizeof(f[op]));
        for (int x = 0; x <= i; x++) {
            for (int y = 0; y <= i; y++) {
                Add(f[op][x][y], f[op ^ 1][x - 1][y - 1]);
                Add(f[op][x][y], 1ll * f[op ^ 1][x][y] * (y + 1) % P);
                Add(f[op][x][y], 1ll * f[op ^ 1][x][y - 1] * (i - y - 1) % P);
            }
        }
        for (int x = 0; x <= i; x++) {
            for (int y = 0; y <= i; y++)
                Add(u[i][x], 1ll * f[op][y][x] * a[y + 1] % P);
            u[i][x] = 1ll * u[i][x] * ifc[i] % P;
        }
    }
    for (int i = 2, op = 0; i <= n; i++, op ^= 1) {
        memset(g[op], 0, sizeof(g[op]));
        for (int x = 0; x <= i; x++) {
            for (int y = 0; y <= i; y++) {
                Add(g[op][x][y], g[op ^ 1][x - 1][y]);
                Add(g[op][x][y], 1ll * g[op ^ 1][x][y] * y % P);
                Add(g[op][x][y], 1ll * g[op ^ 1][x][y - 1] * (i - y) % P);
            }
        }
        for (int x = 0; x <= i; x++) {
            for (int y = 0; y <= i; y++)
                Add(v[i][x], 1ll * g[op][y][x] * b[y + 1] % P);
            v[i][x] = 1ll * v[i][x] * ifc[i] % P;
        }
    }
    for (int i = 0; i < n; i++) 
        for (int x = 0; x <= i; x++) 
            for (int y = 0; x + y + (i != 0) < n; y++) 
                Add(s[i][y], 1ll * u[i][x] * c[x + y + (i != 0)] % P);
    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] % P);
    for (int i = 1; i <= n; i++)
        cout << 1ll * ans[i] * fc[i - 1] % P << ' ';
}

bool Med;
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cerr << (&Mbe - &Med) / 1048576.0 << " MB\n";
    #ifdef FILE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif
    int T = 1;
    // cin >> T;
    while (T--) solve();
    cerr << (int)(1e3 * clock() / CLOCKS_PER_SEC) << " ms\n";
    return 0;
}