CF 1603C Extreme Extension

题目描述

https://codeforces.com/problemset/problem/1603/C

简要题意：给定一个长度为 $n$ 的序列 $a_i$，每次操作可以选择序列中的一个数 $x$，将其变成 $a$ 和 $b$，注意 $a,b$ 插入到原序列 $x$ 的位置，且满足 $a+b=x$，我们定义 $f(l,r)$ 为最少需要多少次操作可以使得序列 $a_l,a_{l+1},\cdots,a_r$ 单调不降，求 $\sum_{i=1}^n\sum_{j=i}^nf(i,j)$

$n,a_i\le 10^5$

Solution

我们首先能够发现两个性质，将 $v$ 分成恰好 $x$ 个数，最小值最大为 $\lfloor\frac{v}{x}\rfloor$；将 $v$ 分成若干个数，满足最大值小于等于 $x$ 且个数最小以及最小值最大，那么会分成 $\lceil\frac{v}{x}\rceil$ 个数，且最小值最大为 $\lfloor\frac{v}{\lceil\frac{v}{x}\rceil}\rfloor$

同时我们发现对于一个序列，最后一个数一定不变，那么答案是固定的，所以我们考虑 $dp$，$f_{i,j}$ 表示从 $n$ 到 $i$，$a_i$ 分解后最小值最大为 $j$ 的答案，同时我们需要另一个数组 $g_{i,j}$ 来记录方案数，注意到第二维只有 $O(\sqrt n)$ 的大小，所以我们直接暴力 $dp$ 即可，本题空间限制略微严格，需要将 $dp$ 数组滚动一下

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#define maxn 100010
#define sqtn 340
using namespace std;

const int p = 998244353;
inline int add(int x, int y) { return (x += y) >= p ? x - p : x; }
inline int mul(int x, int y) { return 1ll * x * y % p; }
inline int add(initializer_list<int> lst) { int s = 0; for (auto t : lst) s = add(s, t); return s; } 

int n, a[maxn];

struct Div_Hash { 
    int id1[sqtn], id2[sqtn], w[sqtn * 2], sn, num, n;
    
    void init(int _n) {
        n = _n, sn = sqrt(n), num = 0; 
        for (int l = 1, r; l <= n; l = r + 1) {
            r = n / (n / l), w[++num] = n / l;
            if (w[num] <= sn) id1[w[num]] = num;
            else id2[n / w[num]] = num;
        }
    }
    int get(int x) { return x <= sn ? id1[x] : id2[n / x]; }
} _;

int f[2][sqtn * 2], g[2][sqtn * 2];
void work() {
    cin >> n; int ans = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    _.init(a[n]), fill(f[n & 1], f[n & 1] + _.num + 1, 0), fill(g[n & 1], g[n & 1] + _.num + 1, 0);
    f[n & 1][_.get(a[n])] = 0, g[n & 1][_.get(a[n])] = 1;
    for (int i = n - 1, s = i & 1, t = s ^ 1; i; --i, swap(s, t)) {
        vector<pair<int, int>> lw;
        for (int j = 1; j <= _.num; ++j) lw.emplace_back(_.get(_.w[j]), _.w[j]);
        _.init(a[i]), fill(f[s], f[s] + _.num + 1, 0), fill(g[s], g[s] + _.num + 1, 0);
        f[s][_.get(a[i])] = 0, g[s][_.get(a[i])] = 1;
        for (auto [k, v] : lw) {
            int j = _.get(a[i] / ((a[i] + v - 1) / v));
            f[s][j] = add({ f[s][j], f[t][k], mul(g[t][k], (a[i] + v - 1) / v - 1) });
            g[s][j] = add(g[s][j], g[t][k]);
        }
        for (int j = 1; j <= _.num; ++j) ans = add(ans, f[s][j]); 
    } cout << ans << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0; 
}