2020CCPC绵阳L. Lottery(组合数学)

标签：std 箱子 Lottery 幂次彩票 int 绵阳 2020CCPC nw

题意：给出你n个箱子，每个箱子有一个对应的指数ai,和数量xi代表这个箱子内的大小为2^ai的彩票有xi张。然后想问你，用这些箱子中的彩票随意选择，最多能组成多少种和不重复的彩票，答案对1e9 + 7取模。
思路：按照所有的幂次排序后，看每一个幂次能不能被表示出来，拆分成二进制。
如果对于一个可以表示成 (1211)_2的段，它可以表示 (2⁴+ 2¹) 种数，根据乘法原理可以得到答案为各个非零连续段的乘积。

代码：

#include <bits/stdc++.h>
#define int long long
const int MOD = 1e9 + 7;

void solve() {
    // 输入
    int n;
    std::cin >> n;
    std::vector<std::pair<int, int>>a(n + 1);
    for (int i = 1; i <= n; ++i) {
        std::cin >> a[i].first >> a[i].second;
    }
    
    // 对幂次排序
    std::sort(a.begin() + 1, a.end());

    // ans 记录答案  l表示当前进行到哪个下标  nw表示当前幂次
    int ans = 1, l = 1, nw;

    while (l <= n) {
        int res = 1;
        int sum = a[l].second;
        nw = a[l].first;     // 更新当前幂次
        l++;

        // 记录一段非0连续段
        std::vector<int>cnt;
        while (true) {
            if (nw == a[l].first && l <= n) {
                sum += a[l].second;
                l++;
            }
            if (sum <= 0 && nw + 1 == a[l].first && l <= n) {
                nw++;
                continue;
            }
            if (sum <= 0) break;
            if (sum <= 2) {
                cnt.push_back(sum);
                sum = 0;
                continue;
            }
            int x = sum % 2;
            if (x == 0) {
                cnt.push_back(2);
                sum -= 2;
            } else if (x == 1) {
                cnt.push_back(1);
                sum -= 1;
            }
            sum /= 2;
            nw++;
        }

        // 计算答案
        int res2 = 0;
        for (int q : cnt) {
            if (q == 2) res2 += res;
            res *= 2;
            res %= MOD;
            res2 %= MOD;
        }

        ans *= (res + res2);
        ans %= MOD;
    }

    std::cout << ans % MOD << '\n';
}

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

    for (int i = 1; i <= _; ++i) {
        std::cout << "Case #" << i << ": ";
        solve();
    }

    return 0;
}

标签：std,箱子,Lottery,幂次,彩票,int,绵阳,2020CCPC,nw
From： https://www.cnblogs.com/MCJ-YMR/p/16793404.html

2020CCPC绵阳L. Lottery(组合数学)

相关文章

赞助商

阅读排行