526互联

[ARC104D] Multiset Mean 题解

发布时间 2023-11-02 21:37:18作者: User-Unauthorized

题意

给定 \(N,K\) 和 \(M\)。对于每个大小在 \([1,N]\) 中的 \(x\)，求每个元素大小在 \([1,N]\) 中，平均数为 \(x\) 且相同元素不超过 \(K\) 个的可重集的数量，对 \(M\) 取模。

\(1 \le N,K \le 100\)，\(M\) 为质数。

题解

发现对于 \(x\)，若存在一个合法的集合 \(S\)，那么有

\[\sum\limits_{y \in S} x - y \left[y < x\right] = \sum\limits_{y \in S} y - x \left[y > x\right] \]

成立，设 \(sum = \sum\limits_{y \in S} x - y \left[y < x\right]\)，那么可以通过枚举 \(sum\) 的值实现计算答案。

现在问题转化为了求使用 \([1, i]\) 中的数构成和为 \(sum\) 的集合的数量，这个问题可以通过背包 \(\tt{DP}\) 解决。

设 \(f_{i, j}\) 表示使用 \([1, i]\) 中的数构成和为 \(j\) 的集合的数量，那么有

\[f_{i, j} = \sum\limits_{x = 0}^{K} f_{i - 1, j - i \times x} \]

直接暴力做的话复杂度为 \(\mathcal{O}(N^4K)\)，写得好的话是可以通过的。

但是我们可以通过使用前缀和优化来通过，这样的话复杂度为 \(\mathcal{O}(N^3K)\)，可以通过。

Code

\(\mathcal{O}(N^4K)\)

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

valueType MOD;

template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a + b;

    if (a >= mod)
        a -= mod;
}

template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a - b;

    if (a < 0)
        a += mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
    return a + b >= mod ? a + b - mod : a + b;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
    return a - b < 0 ? a - b + mod : a - b;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
    return (long long) a * b % mod;
}

template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
    a = (long long) a * b % mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
    T1 result = 1;

    while (b > 0) {
        if (b & 1)
            Mul(result, a, mod);

        Mul(a, a, mod);
        b = b >> 1;
    }

    return result;
}

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

    valueType N, K;

    std::cin >> N >> K >> MOD;

    valueType const S = K * N / 2 * (N / 2 + 1) / 2;

    ValueMatrix F(N + 1, ValueVector(S + 1, 0));

    F[0][0] = 1;

    for (valueType i = 1; i <= N; ++i) {
        F[i] = F[i - 1];

        for (valueType k = 1; k <= K; ++k)
            for (valueType j = std::min(i * k + K * (i - 1) * i / 2, S); j >= i * k; --j)
                Inc(F[i][j], F[i - 1][j - i * k]);
    }

    for (valueType i = 1; i <= N; ++i) {
        valueType ans = 0;

        for (valueType j = 1; j <= S; ++j) {
            if (F[i - 1][j] == 0 || F[N - i][j] == 0)
                break;
            else
                Inc(ans, mul(F[i - 1][j], F[N - i][j]));
        }

        Mul(ans, K + 1);
        Inc(ans, K);

        std::cout << ans << std::endl;
    }

    return 0;
}

\(\mathcal{O}(N^4K)\)

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;

valueType MOD;

template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a + b;

    if (a >= mod)
        a -= mod;
}

template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
    a = a - b;

    if (a < 0)
        a += mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
    return a + b >= mod ? a + b - mod : a + b;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
    return a - b < 0 ? a - b + mod : a - b;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
    return (long long) a * b % mod;
}

template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
    a = (long long) a * b % mod;
}

template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
    T1 result = 1;

    while (b > 0) {
        if (b & 1)
            Mul(result, a, mod);

        Mul(a, a, mod);
        b = b >> 1;
    }

    return result;
}

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

    valueType N, K;

    std::cin >> N >> K >> MOD;

    valueType const S = K * N / 2 * (N / 2 + 1) / 2;

    ValueMatrix F(N + 1, ValueVector(S + 1, 0));

    F[0][0] = 1;

    for (valueType i = 1; i <= N; ++i) {
        F[i] = F[i - 1];

        for (valueType j = i; j <= S; ++j)
            Inc(F[i].at(j), F[i][j - i]);

        for (valueType j = S; j >= i * (K + 1); --j)
            Dec(F[i][j], F[i][j - i * (K + 1)]);
    }

    for (valueType i = 1; i <= N; ++i) {
        valueType ans = 0;

        for (valueType j = 1; j <= S; ++j) {
            if (F[i - 1][j] == 0 || F[N - i][j] == 0)
                break;
            else
                Inc(ans, mul(F[i - 1][j], F[N - i][j]));
        }

        Mul(ans, K + 1);
        Inc(ans, K);

        std::cout << ans << std::endl;
    }

    return 0;
}