首页 > 其他分享 >[ARC104D] Multiset Mean 题解

[ARC104D] Multiset Mean 题解

时间：2023-11-02 21:46:41浏览次数：34  
标签：ARC104D const 题解 T2 T1 template Multiset MOD mod

题意

给定 \(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;
}

标签：ARC104D,const,题解,T2,T1,template,Multiset,MOD,mod
From： https://www.cnblogs.com/User-Unauthorized/p/solution-ARC104D.html

相关文章

  • [ARC104C] Fair Elevator 题解
    题意有\(N\)个区间\([a_i,b_i](a_i<b_i)\)，都是\([1,2n]\)内的整数且互不相同（\(a_i\neb_j,a_i\nea_j,b_i\neb_j\)）。现在给定一些\(a\)和\(b\)的值，剩下不知道的用\(-1\)表示。问是否存在一种替换掉\(-1\)的方案，使得：若两个区间有交，那么它们长度相等。即\(\forall......
  • 题解：USACO23OPEN-Silver
    题解：USACO23OPEN-SilverT1MilkSum给定一个长度为\(N\)的序列\(a_1,a_2,...,a_n\)，现在给出\(Q\)次操作每次将\(a_x\)修改为\(y\)，每次修改后，求将序列重排后的\(T\)的最大值，定义\(T=\sum_{i=1}^{n}i\timesa_i)\)每次修改数组后会将序列还原成原样（修改不继承）有一......
  • CF773A Success Rate 题解
    SuccessRate（提供二分做法）前言听说是史上最简单蓝题，做了一下。题意已知\(x,y,p,q\)，通过只让\(y\)加\(1\)或\(x,y\)同时加\(1\)，使得满足：\[\frac{x'}{y'}=\frac{p}{q}\]思考目标状态为\(\frac{p}{q}\)，考虑到这是个比值，自然\(\frac{x'}{y'}=\frac{kp}{kp}\)。明显......
  • 【POJ 1256】Anagram 题解（全排列）
    描述你要编写一个程序，从一组给定的字母中生成所有可能的单词。示例：给定单词“abc”，您的程序应该-通过探索这三个字母的所有不同组合-输出单词“abc”、“acb”、“bac”、“bca”、“cab”和“cba”。在输入文件中的单词中，某些字母可能出现多次。对于给定的单词，您的程序不应多次......
  • CF1868B2 Candy Party (Hard Version) 题解
    Problem-1868B2-CodeforcesCandyParty(HardVersion)-洛谷相信大家已经看过SimpleVersion，这题和上题不同之处就在于如果\(b_i=2^x\)，他可以被分解成\(2^x\)或\(2^{x+1}-2^x\)，我们不妨起初固定一种方案，如果不满足条件后再把一部分换回去。我们强制钦定起......
  • CF227A Where do I Turn? 题解
    题目大意：\(A\)，\(B\)在一条直线上。\(B\)，\(C\)在一条直线上你从\(A\)走到了\(B\)去\(C\)，问现在应该是直走、左转、还是右转。思路：分类讨论：分别求\(A\)到\(B\)，\(B\)到\(C\)是什么方向，然后可得\(A\)到\(C\)的方向。Code:#include<bits/stdc++.h>usingnamesp......
  • CF333B题解
    分析发现只能跳\(n-1\)次，所以每个点一定是畅通无阻地抵达终点，所以有障碍的行和列放不了，并且每一个行或列最多放一个。因为同时跳，思考会不会跳到一起，发现如果不在正中间可以将起点放到另一头就不会跳到一起，如果在正中间就一定会跳到一起，所以正中间的行和列加一起最多只能放......
  • CF333A题解
    分析被除数一定，除数越小，商越大，所以选择合法的最小\(3_{x}\)。枚举指数即可，复杂度\(\mathcal{O(\log_{3}w)}\)，\(w\)为值域\(1e18\)，可以通过本题。代码#include<iostream>#defineintlonglongusingnamespacestd;constexprintMAXN(1000007);intf[MAXN];int......
  • P9740 「KDOI-06-J」ION 比赛 题解
    题目思路：先计算总分数\(sum\)，\(c_i=\frac{100}{a_i}\)为每道题的每个测试点分数。如果总分数达到\(Au\)线，直接输出AlreadyAu.。否则计算到达\(Au\)线还需多少分\(p\)，遍历所有题，求出每道题的失分，如果失分大于等于\(p\)，则输出\(\lceil\frac{p}{c_i}\rceil\)，即至......
  • Educational Codeforces Round 134 (Div.2) D 题解
    题目链接D.MaximumAND题目大意给定两组序列\(a\)\(b\),长度为\(n\)，现有一新序列\(c\)，长度也为\(n\)。其中，\(c_i=a_i\oplusb_i\)。定义\(f(a,b)=c_1\&c_2\&……\&c_n\)。现在你可以随意编排\(b\)序列的顺序，求\(f(a,b)\)的最大值。思路以下位运算均是......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99