T1. 老魔杖

博弈论。

70 pts 直接遍历状态转移 SG 函数即可。注意数组大小。

#include <bits/stdc++.h>
#define ms(x) memset(x, 0, sizeof x)
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

const int N = 70;
int state[141][71][29][15];

int sg(int a, int b, int c, int d) {
    if(~state[a][b][c][d]) return state[a][b][c][d];
    if(!a && !b && !c && !d) return state[a][b][c][d] = 0;
    int res = 0;
    if(a >= 1) res |= !sg(a - 1, b, c, d);
    if(b >= 2) res |= !sg(a, b - 2, c, d);
    if(c >= 3) res |= !sg(a, b, c - 3, d);
    if(d >= 4) res |= !sg(a, b, c, d - 4);

    if(b >= 1) res |= !sg(a + 2, b - 1, c, d);
    if(c >= 1) res |= !sg(a + 1, b + 1, c - 1, d);
    if(d >= 1) res |= !sg(a + 1, b, c + 1, d - 1);
    if(d >= 1) res |= !sg(a, b + 2, c, d - 1);
    return state[a][b][c][d] = res;
}

int main() {
    memset(state, -1, sizeof state);
    int T = rd();
    while(T--) {
        int a = rd(), b = rd(), c = rd(), d = rd();
        printf("%d\n", sg(a, b, c, d));
    }
    return 0;
}

100pts 做法：

设 r = (a+c) \% 2 ， s = (b + d) \% 3

这个游戏先手必胜当且仅当 r \neq s

证明：

对于必败状态 r = s 所有转移都会造成 r \neq s 即为必胜状态。

对于必胜状态，总存在一种转移会造成 r = s 即为必败状态。

证毕。

T2. 复活石

原式即为多个 1 函数相卷积结果。枚举

#include <bits/stdc++.h>
#define ms(x) memset(x, 0, sizeof x)
#define d(x) cerr << #x << " => " << x << endl
#define dd(x) cerr << x << endl
#define D cerr << "Passed [" << __FUNCTION__ << "] on line " << __LINE__ << endl
#define int long long 
#pragma GCC optimize(2)
using namespace std;
int rd() {
    int f = 1, val = 0; char ch = getchar();
    while(!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
    while(isdigit(ch)) val = val * 10 + ch - '0', ch = getchar();
    return f * val;
}

const int N = 1e5 + 5;
int f[N], g[N], tmp[N], base[21][N];

vector<int> a, factor[N];
void init(int n) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; i * j <= n; j++) {
            factor[i * j].push_back(i);
        }
    }

    for(int i = 1; i <= n; i++) {
        base[0][i] = 1;
    }
}

const int maxn = 100000, mod = 1000000007;
void Merge(int* a, const int* b, const int* c, int n) {
    for(int i = 1; i <= n; i++) {
        tmp[i] = 0;
    }

    for(int i = 1; i <= n; i++) {
        for(auto d : factor[i]) {
            tmp[i] = (tmp[i] + b[d] * c[i / d] % mod) % mod;
        }
    }

    for(int i = 1; i <= n; i++) {
        a[i] = tmp[i];
    }
}

int calc(int x) {
    int res = 0;
    for(auto d : factor[x]) {
        res = (res + g[d] * f[x / d] % mod) % mod;
    }
    return res;
}

signed main() {
    init(maxn);
    for(int i = 1; i <= 20; i++) {
        Merge(base[i], base[i - 1], base[i - 1], maxn);
    }

    int T = rd();
    while(T--) {
        int n = rd(), k = rd();
        for(int i = 1; i <= n; i++) {
            f[i] = rd();
        }

        memset(g, 0, sizeof g);
        g[1] = 1;
        for(int i = 0; i <= 20; i++) {
            if(k & (1 << i)) Merge(g, g, base[i], maxn);
        }

        for(int i = 1; i <= n; i++) {
            printf("%lld ", calc(i));
        }

        puts("");
    }
    return 0;
}

T3. 隐形斗篷

不想改。