[CF1371E2] Asterism (Hard Version) - 组合数学,同余,二分

[CF1371E2] Asterism (Hard Version) - 组合数学,同余,二分

Description

有 n 个敌人，编号为 1～n，第 i 个敌人有 ai 个糖果。Yuzu在最开始时有 x 个糖果。当Yuzu拥有的糖果数大于等于她此时面对的敌人的糖果数时，它可以击败这个敌人，并取得1个糖果，否则她将被敌人击败，并且什么也得不到。Yuzu希望对所有的敌人都取得胜利，请帮她重新安排 n 个敌人的出现顺序，即 1～n 的一个合法的排列 P。让我们定义 f(x) 等于初始时Yuzu有 x 个糖果时这样的排列 P 的数量。给出 n,p，其中 p 是质数，并且 p≤n。 我们称 x 是好的，当且仅当 f(x) 不能被 p 整除。找到所有好的 x。

Solution

首先根据基本的组合有 \(f(x)=\prod_{i=x}^{x+n-1} x-i+t_i\)，其中 \(t_i\) 表示糖数不超过 \(i\) 的人数

\(p \not | f(x)\)，等价于 \(\forall i, x \neq i-t_i \mod p\)

有效的值在 \(\max(a_i)-n\) 到 \(\max(a_i)\) 间寻找即可

数值较大，\(t_i\) 用桶处理不便，考虑直接用二分代替

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

#define int long long

const int N = 1e6 + 5;
int n, p, a[N], cnt[N];

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n >> p;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    a[n + 1] = 1e18;

    vector<int> ans;

    for (int i = a[n] - n + 1; i <= a[n]; i++)
    {
        int tmp = upper_bound(a + 1, a + n + 1, i) - a - 1;
        cnt[((i - tmp) % p + p) % p]++;
    }

    for (int i = max(a[n] - n + 1, 0ll); i <= a[n]; i++)
    {
        if (cnt[i % p] == 0)
            ans.push_back(i);
        int tmp = upper_bound(a + 1, a + n + 1, i) - a - 1;
        cnt[((i - tmp) % p + p) % p]--;
        tmp = upper_bound(a + 1, a + n + 1, i + n) - a - 1;
        cnt[((i + n - tmp) % p + p) % p]++;
    }

    cout << ans.size() << endl;
    for (auto i : ans)
        cout << i << " ";
    cout << endl;
}

[CF1371E2] Asterism (Hard Version) - 组合数学,同余,二分

原文：https://www.cnblogs.com/mollnn/p/14638900.html