下凸子数组

题目大意

现在需要我们生成一个单调递增的数组，并且数组的增量单调不降，数组的首项为1，末尾为 $k$。

题解思路

我们设增量为 $d_i$ , 问题可以转化为存在多少种不同的数组，使得 $\sum^p_{i=1}{d_i} = k-1$，问题可以转换为一个完全背包问题。

参考代码

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int32_t;
using i128 = __int128;

namespace myMath {
    i64 mod = 998244353;

    i64 add(i64 x, i64 y) {
        x += y;
        if (x > mod) x -= mod;
        return x;
    }

    i64 sub(i64 x, i64 y) {
        x -= y;
        if (x < 0)x += mod;
        return x;
    }

    i64 mul(i64 x, i64 y) {
        x *= y;
        x -= x / mod * mod;
        return x;
    }

    i64 qpow(i64 x, i64 y) {
        i64 res = 1;
        while (y) {
            if (y & 1) res = mul(res, x);
            y >>= 1;
            x = mul(x, x);
        }
        return res;
    }

    i64 inv(i64 x) {
        return qpow(x, mod - 2);
    }

    i64 qdiv(i64 x, i64 y) {
        return mul(x, inv(y));
    }

    void set_mod(i64 x) {
        mod = x;
    }

    namespace Comb {
        int n;
        vector<i64> fa;
        vector<i64> ifa;

        void init(int _n) {
            n = _n;
            fa.assign(n + 1, 1), ifa.assign(n + 1, 1);
            for (int i = 1; i <= n; i++) fa[i] = mul(fa[i - 1], i);
            ifa[n] = inv(fa[n]);
            for (i64 i = n - 1; i; i--) {
                ifa[i] = mul(ifa[i + 1], i + 1);
            }
        }

        i64 C(int i, int j) {
            return mul(fa[i], mul(ifa[j], ifa[i - j]));
        }
    }

    //线性求逆元

    vector<i64> get_inv(int k) {
        vector<i64> in(k + 1, 1);
        for (int i = 2; i <= k; i++) {
            in[i] = mul(in[mod % i], sub(mod, mod / i));
        }
        return in;
    }
}

using namespace myMath;


int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    vector<i64> f(5000 ,0 );
    f[0] = 1;
    for (int i = 1; i <= 5000; i++) {
        for (int j = i ; j <= 5000; j++) {
            f[j] = add(f[j], f[j - i]);
        }
    }

    int t;
    cin >> t;
    for (int i = 1; i <= t; i++) {
        int x;
        cin >> x;
        cout << f[x - 1 ] << endl;
    }
}