D – Numbers of Permutations

思考量很小的一道题。

先用间接法来算。初始答案为\(n!\)，然后考虑容斥掉那些符合排序规则的方案。发现，我们可以分开来考虑，按照容斥的顺序：先考虑只算第一维、第二维的，在加回来两维都考虑的。

第一维和第二维的做法非常显然：排序之后用多重集的排列就行了，考虑每一个相同的区间里面内部乘起来。如果有\(k\)个连续的数段，那么部分的答案就是\(\prod_{i = 1}^l len_k!\)。

两维皆有的情况稍微复杂一点。首先，如果按照第一维优先排序的方式，发现序列无法保证第二维单调不降，那么双维皆有的情况就不存在；反之，我们扫描第一维分出第一维的数段，然后在每一个数段里统计每一种数的个数，然后第三维就是这些「保证第一维相同的第二维数段」的答案。

// CF1207D.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 3e5 + 200, mod = 998244353;

pair<int, int> nodes[MAX_N];

int fac[MAX_N], n;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &nodes[i].first, &nodes[i].second);
    for (int i = fac[0] = 1; i <= n; i++)
        fac[i] = 1LL * fac[i - 1] * i % mod;
    int ans[4] = {fac[n], 1, 1, 1};
    for (int c = 1; c <= 2; c++)
    {
        sort(nodes + 1, nodes + 1 + n);
        int l = 1, r;
        while (l <= n)
        {
            r = l + 1;
            while (r <= n && nodes[r].first == nodes[l].first)
                r++;
            ans[c] = 1LL * ans[c] * fac[r - l] % mod;
            l = r;
        }
        ans[0] = (1LL * ans[0] + 1LL * (mod - ans[c])) % mod;
        for (int i = 1; i <= n; i++)
            swap(nodes[i].first, nodes[i].second);
    }
    int l = 1, r;
    sort(nodes + 1, nodes + 1 + n);
    while (l <= n)
    {
        r = l + 1;
        while (r <= n && nodes[r].first == nodes[l].first)
            r++;
        map<int, int> mp;
        mp.clear();
        for (int i = l; i < r; i++)
            mp[nodes[i].second]++;
        for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++)
            ans[3] = 1LL * ans[3] * fac[(*it).second] % mod;
        l = r;
    }
    for (int i = 2; i <= n; i++)
        if (nodes[i].second < nodes[i - 1].second)
            ans[3] = 0;
    ans[0] = (1LL * ans[0] + 1LL * ans[3]) % mod;
    printf("%d", ans[0]);
    return 0;
}

E – XOR Guessing

sb 题。

考虑把一个 14 位的二进制数分为前 7 位和后 7 位。欲获取两段，保证每次询问时空出前七位或者后七位，然后拼起来就行了。

// CF1207E.cpp
#include <bits/stdc++.h>

using namespace std;

int main()
{
    fflush(stdout);
    cout << "? ";
    for (int i = 1; i < 100; i++)
        cout << i << " ";
    cout << 100 << endl;
    fflush(stdout);
    int ans1, ans2;
    cin >> ans1;
    fflush(stdout);
    cout << "? ";
    for (int i = 1; i < 100; i++)
        cout << (i << 7) << " ";
    cout << 12800 << endl;
    fflush(stdout);
    cin >> ans2;
    int mask1 = 0;
    for (int i = 0; i < 7; i++)
        mask1 |= (1 << i);
    int mask2 = mask1 << 7;
    cout << "! " << ((ans1 & mask2) | (ans2 & mask1)) << endl;
    return 0;
}

F – Remainder Problem

真的是暴力出奇迹啊，分块好题。

把问题简化一下，大概就是：

1. 支持修改
2. 给出块的大小\(x\)，求出每一个块中块内下标为\(y\)的和。

首先，对于块大小\(x\)大的情况，回答询问只需要\(O(\lfloor \frac{n}{x} \rfloor)\)的时间就可以搞定了。如果块的大小比较小，比如说设置一个临界值\(k\)，那么最多只会存在\(k^2\)级别的询问，除掉一个\(k\)，也就说明每次修改只会影响到\(k\)个询问。所以，我们每次修改的时候对于每一个小于\(k\)的块长进行预处理，这样\(x\)小的时候就可以进行\(O(1)\)的回答了。

显然，\(k = \sqrt{n}\)。

// CF1207F.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5 + 200, MAX_K = 750;

int sum[MAX_K][MAX_K], ai[MAX_N];

int main()
{
    int q;
    scanf("%d", &q);
    while (q--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1)
        {
            ai[x] += y;
            for (int i = 1; i < MAX_K; i++)
                sum[i][x % i] += y;
        }
        else if (x >= MAX_K)
        {
            int ans = 0;
            for (int i = y; i <= 500000; i += x)
                ans += ai[i];
            printf("%d\n", ans);
        }
        else
            printf("%d\n", sum[x][y]);
    }
    return 0;
}