自动搬运

查看原文

来自洛谷，原作者为

	GuWolf 为什么不问问神奇海螺呢

搬运于2025-08-24 23:12:24，当前版本为作者最后更新于2025-04-08 23:06:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

基础情况分析

首先，我们分析当 $n = \frac{m \times (m + 1)}{2}$ 中最小值的情况，使用以下代码暴力求出前 $10$ 个最小值：

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int i = 2; i <= 11; ++i) {
        int mn = INT_MAX;
        vector<int> a(i);
        for (int j = 0; j < i; ++j) a[j] = j + 1;

        do {
            int tmp = a[0] * a[i - 1];
            for (int j = 1; j < i; ++j) tmp += a[j] * a[j - 1];
            mn = min(mn, tmp);
        } while (next_permutation(a.begin(), a.end()));
        
        cout << mn << ' ';
    }
    return 0;
}

求得前 $10$ 个最小值分别为：

4 11 21 37 58 87 123 169 224 291

此时，我们对它进行三阶差分。

可以看到，第三阶的值在 $3$ 和 $-1$ 间交替变化。

拓展分析

接下来拓展到 $n > \frac{m \times (m + 1)}{2}$ 的情况。

很容易可以看到，当把多出来的值分配给 $a_i$ 时，对总值的贡献是 $a_i \times (a_{i-1} + a_{i+1})$。

进而发现，$n$ 每增加 $1$ 的时候，对总值最小的贡献是 $3$ (当 $a_i$ 的两边分别为 $1$、$2$ 的时候)

注意: 此时还需特判 $n = 2$ 的情况。

if (m == 2) {
    cout << (n - 1 + n - 1) % MOD << endl;
    return;
}

完整代码

#include <bits/stdc++.h>

#define LL long long
#define endl '\n'

using namespace std;

const LL MOD = 998244353;
LL d[4][200010], tmp[] = {-1, 3};

void solve() {
    LL n, m;
    cin >> m >> n;

    if (m == 2) {
        cout << (n - 1 + n - 1) % MOD << endl;
        return;
    }

    for (int i = 1; i < 200005; ++i) d[3][i] = tmp[i & 1];
    d[2][1] = 3;
    d[1][1] = 7;
    d[0][1] = 4;
    for (int i = 1; i < 200005; ++i) {
        d[2][i + 1] = (d[2][i] + d[3][i]) % MOD;
        d[1][i + 1] = (d[1][i] + d[2][i]) % MOD;
        d[0][i + 1] = (d[0][i] + d[1][i]) % MOD;
    }
    n -= m * (m + 1) / 2ll;
    cout << (d[0][m - 1] + 3ll * n) % MOD << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while (T--) solve();
    return 0;
}