A – 礼物

sb 暴力出奇迹，欺骗人的感情。

敢情您特么\(1e9\)的复杂度都能过？真的服气。

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

using namespace std;

const int MAX_N = 1010;

int prefix[MAX_N][MAX_N], suffix[MAX_N][MAX_N];
int n, ai[MAX_N], bi[MAX_N], ci[MAX_N], m;

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d%d", &ai[i], &bi[i], &ci[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < MAX_N; j++)
        {
            prefix[i][j] = prefix[i - 1][j];
            if (j >= ai[i])
                prefix[i][j] = max(prefix[i][j], prefix[i - 1][j - ai[i]] + bi[i]);
        }
    for (int i = n; i >= 1; i--)
        for (int j = 0; j < MAX_N; j++)
        {
            suffix[i][j] = suffix[i + 1][j];
            if (j >= ai[i])
                suffix[i][j] = max(suffix[i][j], suffix[i + 1][j - ai[i]] + bi[i]);
        }
    scanf("%d", &m);
    while (m--)
    {
        int del, money;
        scanf("%d%d", &del, &money), del++;
        int ans = 0;
        for (int i = 0; i <= money; i++)
            ans = max(ans, prefix[del - 1][i] + suffix[del + 1][money - i]);
        printf("%d\n", ans);
    }
    return 0;
}

B – 异或

这道题太特么傻逼了。

考虑一个位有可能作为答案的贡献，当且仅当之前的位都相等。在 Trie 树上，任意一个节点都可以保证前缀相等，所以每一个节点的贡献就是\(2^{len} \times son_0 \times son_1\)。

// B.cpp
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int MAX_N = 1e5 + 200;
const ll mod = 199907210507;

struct node
{
    int ch[2];
    ll val;
} nodes[MAX_N * 70];

ll ptot = 1, n, arr[MAX_N], ans, pow2[70];

void insert(ll x)
{
    int p = 1;
    for (int i = 0; i <= 62; i++)
    {
        int bit = (x >> i) & 1;
        if (nodes[p].ch[bit] == 0)
            nodes[p].ch[bit] = ++ptot;
        nodes[p].val++, p = nodes[p].ch[bit];
    }
}

void dfs(int u, int cnt)
{
    if (u == 0)
        return;
    (ans += 1LL * nodes[nodes[u].ch[0]].val * nodes[nodes[u].ch[1]].val % mod * pow2[cnt]) %= mod;
    dfs(nodes[u].ch[0], cnt + 1), dfs(nodes[u].ch[1], cnt + 1);
}

int main()
{
    scanf("%lld", &n);
    for (int i = pow2[0] = 1; i < 70; i++)
        pow2[i] = 1LL * pow2[i - 1] * 2 % mod;
    for (int i = 1; i <= n; i++)
        scanf("%lld", &arr[i]), insert(arr[i]);
    dfs(1, 0), printf("%lld", 1LL * ans * 2 % mod);
    return 0;
}

C – 子集

非常奇妙的一道题。

答案是\(2^{n \times k}\)。我想了很久的原因来解释这个答案，也感谢 XG_Zepto 和 CrazyDave 的思考。我们可以发现，选择一种单调（非偏序的）的点集合，并往这样的集合里面填入数字即可确定整个方案。

我们指「非偏序的点」，形如图中两个 B 点的关系：

A
^
|
A <- A
^    ^
|    |
A <- A <- B
^    ^    ^
|    |    |
A <- B <- A <- A

定义这样的点为某个元素最早存在的点，往这样的点中放元素可以让上游的区域全部覆盖该元素。考虑有\(2^k\)个这样的点集合（也就是「非偏序的点」组成的集合的子集个数），然后每个元素放入某个集合，那么元素个数就是\(2^{nk}\)。

大概这样，我还需要再进行思考。

关于「非偏序的点」组成的集合的子集个数为\(2^k\)的证明 from XG_Zepto：

记\(f(k)\)为从第\(k\)行开始向上的非偏序点集合个数，考虑第\(k\)行包括了之前的所有情况，所以\(f(k) = 2 + \sum_{i = 1}^{k – 1} f(i)\)，然后这个\(2\)代表着独占情况。

大概就是这样。

// C.cpp
#include <bits/stdc++.h>
#define ll unsigned long long

using namespace std;

const ll mod = 7528443412579576937;

ll quick_mul(ll x, ll y)
{
    ll res = 0;
    if (x < y)
        swap(x, y);
    while (y)
    {
        if (y & 1LL)
            res = (res + x < mod) ? (res + x) : (res + x - mod);
        x = (x + x < mod) ? (x + x) : (x + x - mod);
        y >>= 1LL;
    }
    return res;
}

ll quick_pow(ll bas, ll tim)
{
    ll ans = 1;
    while (tim)
    {
        if (tim & 1LL)
            ans = quick_mul(ans, bas);
        bas = quick_mul(bas, bas);
        tim >>= 1LL;
    }
    return ans;
}

int main()
{
    ll n, k;
    scanf("%lld%lld", &n, &k), printf("%lld", quick_pow(2, 1LL * n * k));
    return 0;
}