7.14暑期模拟赛

2022暑

---

T1 brick

考虑没有奖励砖，那么每一列独立，稍微推一下可以发现是一个背包的模型

设：$f(i,j)$ 表示前 $i$ 列还剩 $j$ 颗子弹的最大答案，$Val(i,k)$ 为第 $i$ 列打 $k$ 个能得到的价值。

$$f(i,j) = \max\{{f(i - 1, j + k) + Val(i, k)\}}$$

考虑加入奖励砖，一个很显然的想法，记录 $bk(i,j)$ 表示第 $i$ 列打到第 $j$ 行要消耗的子弹：

$$f(i,j) = \max\{{f(i - 1, j + bk(i, k)) + Val(i, k)\}}$$

但这样会有个问题，当子弹为 $0$ 时，下一个是打奖励砖，按照这个方程是打不到这块奖励砖的。

但实际上我们知道，可以通过交换列的顺序打到这块砖，但再手玩几组会发现，这种情况比较复杂，不是很好判断。

题解里给了一个十分神奇的想法，单独拎出最后一颗子弹不打，给 DP 数组增添一维

$f(i,j,0/1)$ 表示前 $i$ 列，还剩 $j$ 枚子弹，$0$ 表示没有确定最后一颗子弹的位置，$1$ 表示已经确定。

分 $0,1$ 先按照上面的方程转移，但还需要加上一步转移。

当目前的砖是一块普通砖时，可以确定最后一枚子弹打到这块砖上，那么就是：

$$f(i,j,1) = \max\{{f(i - 1, j + bk(i, k) - 1,0) + Val(i, k)\}}$$

答案取 $0, 1$ 的 $\max$ 即可

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 205;
int n, m, k;
int a[maxn][maxn], b[maxn][maxn], f[maxn][maxn][2], Answer;
signed main() {
//  freopen("brick.in", "r", stdin);
//  freopen("brick.out", "w", stdout);
    n = read(), m = read(), k = read();
    if(k == 0) { printf("0\n"); return 0; }
    k--;
    for(register int i = n; i >= 1; --i)
        for(register int j = 1; j <= m; ++j) a[i][j] = read();
    for(register int i = n; i >= 1; --i)
        for(register int j = 1; j <= m; ++j) b[i][j] = read();
    for(register int j = 1; j <= m; ++j) {
        for(register int p = 0; p <= k; ++p) f[j][p][0] = f[j - 1][p][0], f[j][p][1] = f[j - 1][p][1];
        int Val = 0, Cnt = 0; 
        for(register int i = 1; i <= n; ++i) {
            Val += a[i][j], Cnt += (b[i][j] ^ 1);
            for(register int p = 0; p + Cnt <= k; ++p) {
                f[j][p][0] = max(f[j][p][0], f[j - 1][p + Cnt][0] + Val);
                f[j][p][1] = max(f[j][p][1], f[j - 1][p + Cnt][1] + Val);
            }
            if(!b[i][j]) {
                for(register int p = 0; p + Cnt - 1 <= k; ++p)
                    f[j][p][1] = max(f[j][p][1], f[j - 1][p + Cnt - 1][0] + Val);
            }
        }
    }
    for(register int i = 0; i <= k; ++i) Answer = max(Answer, max(f[m][i][0], f[m][i][1]));
    printf("%lld\n", Answer);
    return 0;
}

T2 math

简单推柿子题。

可以令：$a^i + b^i + c^i = f(i)$ 其中 $f(1) = n, f(2) = m, f(3) = k$

我们先推 $f(i)$ 的递推式，由于

$$(a^i + b^i + c^i) = (a ^ {i - 1} + b ^ {i - 1} + c ^{i - 1}) \times (a + b + c) - \sum_{\operatorname{cyc}}{ab\times(a ^{i - 2} + b ^{i - 2})}$$

把一些东西用 $f$ 来表示：

$$f(i) = f(i - 1) * f(1) - \sum_{\operatorname{cyc}}{ab}\times(f(i - 2) - c ^{i - 2})$$

把括号拆开，再提出来一些东西：

$$f(i) = f(i - 1) * f(1) - f(i - 2)\times\sum_{\operatorname{cyc}}{ab} + abc\times f(i - 3)$$

那么只需要用 $f$ 表示出 $\sum{ab}$ 和 $abc$ 就好了。

将 $(a + b + c) ^ 2$ 展开：

$$(a + b + c) ^ 2 = (a ^ 2 + b ^ 2 + c ^ 2) - 2 \times\sum_{\operatorname{cyc}}{ab}$$

所以

$$\sum_{\operatorname{cyc}}{ab} = \frac{n ^ 2 - m}{2}$$

将 $f(3)$ 用 $f(1)$ 与 $f(2)$ 表示：

$$a^3 + b^3 + c^3 = (a ^ 2 + b ^ 2 + c ^ 2) \times (a + b + c) - (a + b + c) \times\sum_{\operatorname{cyc}}{ab} + 3abc$$

所以

$$abc = \frac{1}{2}nm-\frac{1}{6}n^3-\frac{1}{3}k$$

把它们代到递推式中：

$$f(i) = f(1) \times f(i - 1) - \frac{n ^ 2 - m}{2} \times f(i - 2) - (\frac{1}{2}nm-\frac{1}{6}n^3-\frac{1}{3}k)\times f(i - 3)$$

(柿子虽长但很好推)

但这题要求分数形式输出，所以要全程用分数运算。

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 35;
int n, m, k, p;
struct node {
    int fz, fm;
}f[maxn];
inline int Gcd(int x, int y) { return y ? Gcd(y, x % y) : x; }
inline node operator + (node x, node y) {  
    node z; int g = Gcd(x.fm, y.fm);
    z.fm = x.fm / g * y.fm;
    z.fz = x.fz * (z.fm / x.fm) + y.fz * (z.fm / y.fm);
    g = Gcd(z.fz, z.fm), z.fm /= g, z.fz /= g;
    return z;
}
inline node operator -(node x, node y) { y.fz = -y.fz; return x + y; }
inline node operator *(node x, node y) {
    node z;
    z.fz = x.fz * y.fz, z.fm = x.fm * y.fm;
    int g = Gcd(z.fz, z.fm); z.fz /= g, z.fm /= g;
    return z;
}
inline node operator /(node x, node y) { swap(y.fz, y.fm); return x * y; }
signed main() {
//  freopen("math.in", "r", stdin);
//  freopen("math.out", "w", stdout);
    n = read(), m = read(),  k = read(), p = read();
    f[1].fz = n, f[2].fz = m, f[3].fz = k;
    for(register int i = 1; i <= p; ++i) f[i].fm = 1;
    for(register int i = 4; i <= p; ++i) f[i] = (f[1] * f[i - 1]) - ((f[1] * f[1] - f[2]) * (node){1, 2} * f[i - 2]) - ((f[1] * f[2] * (node){1, 2}) - (f[1] * f[1] * f[1] * (node){1, 6}) - (f[3] * (node){1, 3})) * f[i - 3];
    printf("%lld/%lld", f[p].fz, f[p].fm);
    return 0;
}

T3 xor

一位伟大的哲学家说过：“10道xor的题，有8道是Trie树，1道是线性基，剩下1道是乱搞”

所以考虑先把所有串插进 $\operatorname{Trie}$ 树，$\operatorname{lowbit}(x)$ 求出的是 $x$ 二进制最后的 $1$

考虑把所有串倒过来插，把每个串丢到 $\operatorname{Trie}$ 树上查询，如果有与当前位 $\operatorname{xor}$ 为 $1$ 的点，就把答案加上其位权乘上经过此点的串数量。

应该算经典套路了。

//The Code Is From Dawn
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? - x : x;
}
const int maxn = 1e5 + 5, mod = 199907210507;
int n, len;
int a[maxn], num[65], Siz[maxn * 60], Trie[maxn * 60][2], tot, Answer;
inline void Change(int x) {
    for(register int i = 1; i <= len; ++i) num[i] = 0;
    int Cnt = 0;
    while(x) num[++Cnt] = x % 2, x >>= 1;
}
inline int Ksm(int x, int y) {
    int res = 1;
    while(y) {
        if(y & 1) res = res * x % mod;
        x = x * x % mod, y >>= 1;
    }
    return res;
}
inline void Insert(int now) {
    Change(now);
    int x = 0;
    for(register int i = 1; i <= len; ++i) {
        int ch = num[i];
        if(!Trie[x][ch]) Trie[x][ch] = ++tot;
        ++Siz[Trie[x][ch]], x = Trie[x][ch];
    }
}
inline void Solve(int x, int now) {
    if(now == len + 1) return ;
    if(Trie[x][num[now] ^ 1]) Answer = (Answer + Ksm(2, now - 1) * Siz[Trie[x][num[now] ^ 1]] % mod) % mod;
    if(Trie[x][num[now]]) Solve(Trie[x][num[now]], now + 1);
    return ;
}
signed main() {
//  freopen("xor.in", "r", stdin);
//  freopen("xor.out", "w", stdout);
    n = read(), len = 60;
    for(register int i = 1; i <= n; ++i) a[i] = read(), Insert(a[i]);
    for(register int i = 1; i <= n; ++i) {
        Change(a[i]);
        Solve(0, 1);
    }
    printf("%lld\n", Answer);
    return 0;
}