A 小月的奇偶灯控

知识点：异或、奇偶性

$$奇 \oplus 奇 = 奇\\奇 \oplus 偶 = 偶$$
将三个数字异或，异或为 $1$ 时输出 $\texttt{ON}$，否则输出 $\texttt{OFF}$ ，求和判奇偶也可以。

时间复杂度 $\mathcal{O}(1)$ 。

void solve() {
    int s = 0;
    // 异或
    for (int i = 0, x; i < 3; ++i) cin >> x, s ^= x;
    cout << (s ? "ON" : "OFF") << endl;
    // 和
    for (int i = 0, x; i < 3; ++i) cin >> x, s += x;
    cout << (s & 1 ? "ON" : "OFF") << endl;
}

B 小月的立方体

知识点：空间坐标、分类计数

对于点 $(x,y,z)$ ，它关于中心的对称点为 $(a-x,a-y,a-x)$ 。对于第 $i$ 层，枚举不共对角线的四个点即可，为
$$(i,i,i),(n-i,i,i),(i,n-i,i),(n-i,n-i,i)$$
交点同时位于多条对角线时（ $i=n-i$ ）自然会被重复计入。

时间复杂度 $\mathcal{O}((a+1)^3)$ 。

void solve() {
    int a;
    cin >> a;
    vector<vector<vector<int>>> v(a + 1, vector<vector<int>>(a + 1, vector<int>(a + 1)));
    for (int i = 0; i <= a; ++i)
        for (int j = 0; j <= a; ++j)
            for (int k = 0; k <= a; ++k) cin >> v[i][j][k];
    int ans = 0;
    for (int i = 0; i <= a; ++i) ans += v[i][i][i] + v[a - i][i][i] + v[i][a - i][i] + v[a - i][a - i][i];
    cout << ans << endl;
}

C 小月的密码锁

知识点：枚举、循环位移、前缀和

范围不大，直接暴力即可，枚举分割点和偏移次数，然后 $O(n)$ 检查。

时间复杂度 $\mathcal O(25n^2)$

void solve() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    auto next = [&](char c, int x) -> char { return (c - 'A' + x) % 5 + 'A'; };
    int ans = n;
    for (int c = 0; c <= n; ++c) {
        for (int p = 0; p < 5; ++p) {
            for (int q = 0; q < 5; ++q) {
                int x = 0;
                for (int k = 0; k < n; ++k) x += next(s[k], k < c ? p : q) != t[k];
                ans = min(ans, x);
            }
        }
    }
    cout << ans << endl;
}

当然利用前缀和进行维护也可以

偏移量只有 $5$ 种。设 $pre_d[i]$ 表示前 $i$ 位统一循环移动 $d$ 次后的不同位数，则固定分界点 $c$ 与偏移量 $p,q$ 的总代价为：
$$pre_p[c]+pre_q[n]-pre_q[c].$$
预处理全部 $5$ 个偏移量的前缀代价，再枚举 $c,p,q$ 即可。

时间复杂度 $\mathcal{O}(25n)$。

void solve() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    vector<vector<int>> pre(5, vector<int>(n + 1));
    for (int p = 0; p < 5; ++p)
        for (int i = 0; i < n; ++i)
            pre[p][i + 1] = pre[p][i] + ((s[i] - 'A' + p) % 5 + 'A' != t[i]);
    int ans = n;
    for (int c = 0; c <= n; ++c)
        for (int p = 0; p < 5; ++p)
            for (int q = 0; q < 5; ++q)
                ans = min(ans, pre[p][c] + pre[q][n] - pre[q][c]);
    cout << ans << endl;
}

D 小月的电台

知识点：状态压缩、子集和变换、补集计数

设 $f_s$ 为支持集合恰为掩码 $s$ 的电台数。

方法 $\texttt{1}$ ：

两台电台可以通信，当且仅当它们的掩码按位与不为 $0$ ，所以我们直接枚举掩码，对于一组合法的掩码对，产生的无序数对为
$$a_{i,j} = \begin{cases}\binom{f_i}{2}&,i = j\\ f_if_j&,i\neq j\end{cases}$$
求和即可
$$ans = \sum_{0\leq i<j<2^n}a_{i,j}$$
时间复杂度 $\mathcal O(2^{2m})$ 。

void solve() {
    int n, m;
    cin >> n >> m;
    int N = 1 << m, all = N - 1;
    vector<int> f(N);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int x = 0;
        for (auto v : s) (x <<= 1) |= v - '0';
        ++f[x];
    }
    int ans = 0;
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            if (i & j) {
                if (i == j)
                    ans += f[i] * (f[i] - 1) / 2;
                else
                    ans += f[i] * f[j];
            }
    cout << ans << endl;
}

方法 $\texttt{2}$ ：

两台电台不能通信，当且仅当它们的掩码按位与为 $0$ ，直接计算总对数与不可通信对数之差即可。

记 $g_s$ 为 $s$ 的子集掩码出现的次数之和，即 $g_s=\sum_{t\subseteq s}f_t$ 。对于非零掩码 $s$，与其不相交的非零掩码数量为 $g_{\overline{s}}-f_0$ （ $\overline{s}$ 为 $s$ 的有效位按位取反），每对会被计算 $2$ 次。掩码为 $0$ 的电台则与所有电台都不能通信，需要单独计算：
$$bad=f_0(n-f_0)+\binom{f_0}{2}+\frac12\sum_{s=1}^{2^m-1}f_s\left(g_{\overline{s}}-f_0\right).$$
答案为 $\binom n2-bad$。

注：$1\ll i$ 是必然枚举不到 $0$ 的，所以不用特意去减。

时间复杂度 $\mathcal{O}(nm+m2^m)$ 。

void solve() {
    int n, m;
    cin >> n >> m;
    int N = 1 << m, all = N - 1;
    vector<int> f(N);
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        int x = 0;
        for (auto v : s) (x <<= 1) |= v - '0';
        ++f[x];
    }
    vector<int> g = f;
    for (int i = 0; i < m; ++i)
        for (int s = 0; s < N; ++s)
            if (s >> i & 1)
                g[s] += g[s ^ (1 << i)];
    int bad = 0;
    for (int s = 1; s < N; ++s) bad += f[s] * g[all ^ s];
    cout << n * (n - 1) / 2 - bad / 2 << endl;
}

E 小月的折月门牌

知识点：格雷码、位运算、逆变换、区间交

如果你知道格雷码是什么

设 $z$ 从低位到高位的第 $i$ 位为 $z_i$。由于门牌号是格雷码翻转得到的，有：
$$z_i=g_{k-1-i}$$
而格雷码反解满足：
$$b_{k-1}=z_0,\qquad b_{k-2}=z_0\oplus z_1,\qquad b_{k-3}=z_0\oplus z_1\oplus z_2,\dots$$
所以直接从 $z$ 的低位向高位扫一遍，维护前缀异或，就能得到 $x-1$ 的高 $h$ 位 $pref$ 。满足条件的位置是：
$$[pref\cdot2^{k-h}+1,\ (pref+1)\cdot2^{k-h}]$$
令 $b=x-1$，其格雷码为 $g=b\oplus(b\gg1)$。翻转后取低 $h$ 位，等价于取 $g$ 的高 $h$ 位，因此：
$$c_x\bmod 2^h=z\iff g\text{ 的高 }h\text{ 位}=\operatorname{rev}_h(z).$$
将该高位格雷码逆变换，得到 $b$ 的高 $h$ 位为 $u$。令 $len=2^{k-h}$，满足条件的所有位置恰为：
$$x\in[u\cdot len+1,(u+1)\cdot len].$$
与查询区间求交即可。

如果你不知道格雷码是什么

设 $cnt=x-1$。把它的二进制从高到低写出来，$mid$ 的含义很简单：

$mid$ 的最高位等于 $cnt$ 的最高位；
之后每一位表示 $cnt$ 相邻两位是否不同，相同则为 $0$，不同则为 $1$。

即若 $cnt = (a_0a_1a_2…a_m)_2$

接着把 $mid$ 的二进制位反转，于是，门牌号码 $c_x$ 的低 $h$ 位，恰好对应 $mid$ 的高 $h$ 位。

\begin{matrix} cnt &= (&a_0 &a_1 &a_2 &\cdots &a_m)_2\\ \lfloor\frac{cnt}{2}\rfloor &= (&&a_0 &a_1 &\cdots &a_{m-1})_2\\ mid=cnt\oplus \lfloor\frac{cnt}{2}\rfloor &= (&a_0 &a0\oplus a_1 &a_1\oplus a_2 &\cdots &a_m\oplus a_{m-1})_2 \end{matrix}

把 $z$ 从低位到高位读。第一个 $\texttt{bit}$ 直接给出 $cnt$ 的最高位；之后每个 $\texttt{bit}$ 都告诉我们下一位是否要翻转：

$\texttt{bit}$ 为 $\texttt{0}$：下一位和上一位相同；
$\texttt{bit}$ 为 $\texttt{1}$：下一位和上一位不同。

也就是说，$cnt=x-1$ 的高 $h$ 位被唯一确定为 $pref$，但剩余 $k-h$ 位可以任意取值。因此：
$$cnt\in[pref\cdot2^{k-h},(pref+1)\cdot2^{k-h}-1].$$
$x=cnt+1$，合法位置恰好是一段连续区间：
$$x\in[pref\cdot2^{k-h}+1,(pref+1)\cdot2^{k-h}]$$
最后和查询区间 $l,r$ 求交即可。

时间复杂度 $\mathcal{O}(qk)$ 。

void solve() {
    int k, q;
    cin >> k >> q;
    while (q--) {
        int l, r, h, z;
        cin >> l >> r >> h >> z;
        int pref = 0, cur = 0;
        for (int i = 0; i < h; ++i) cur ^= (z >> i) & 1, pref = (pref << 1) | cur;
        int len = 1LL << (k - h), L = pref * len + 1, R = (pref + 1) * len;
        cout << max(0LL, min(r, R) - max(l, L) + 1) << endl;
    }
}

F 小月的二进制分数

知识点：构造、循环节、长除法、分类讨论

设所有串总长度为 $m$。若 $q=2^m-1$，且 $p$ 的 $m$ 位二进制表示为 $R$，则：
$$\frac{p}{q}=0.\overline{R}_2.$$
因此只要把所有字符串拼成 $T$，再循环移位成以 $\texttt{0}$ 开头的 $R$，就能让 $R$ 的循环节包含所有原串。

若出现连续 $1000$ 个 $\texttt{1}$，设这段开始前余数为 $r$，则连续输出后有：
$$r_{1000}=2^{1000}r-(2^{1000}-1)q\ge0.$$
结合 $r<q$ 可得 $q\ge2^{1000}$，超过题目的长度限制，因此无解。

剩余情况，全为 $\texttt{0}$ 时，取 $p=1,q=2^{999}$，从第 $1000$ 位起全为 $\texttt{0}$。全为 $\texttt{1}$ 时，令 $L$ 为最长串长，取 $p=2^L-1,q=2^{L+1}-1$，循环节为 $\texttt{0}\texttt{1}^L$。

时间复杂度 $\mathcal{O}(m)$ 。

void solve() {
    int n, mx = 0, k = 0;
    cin >> n;
    vector<int> st(n);
    string T;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        k = max<int>(k, s.size());
        st[i] = T.size();
        T += s;
        int cur = 0;
        for (auto c : s) {
            if (c == '1')
                mx = max(mx, ++cur);
            else
                cur = 0;
        }
    }
    if (mx == 1000) return cout << -1 << endl, void();
    if (T.find('1') == string::npos) {
        cout << "1" << endl;
        cout << '1' << string(999, '0') << endl;
        for (int i = 0; i < n; ++i) cout << 1000 << " \n"[i + 1 == n];
        return;
    }
    if (T.find('0') == string::npos) {
        cout << string(k, '1') << endl;
        cout << string(k + 1, '1') << endl;
        for (int i = 0; i < n; ++i) cout << 2 << " \n"[i + 1 == n];
        return;
    }
    int m = T.size(), cut = T.find('0');
    string R = T.substr(cut) + T.substr(0, cut);
    cout << R.substr(R.find('1')) << endl;
    cout << string(m, '1') << endl;
    for (int i = 0; i < n; ++i) {
        int a = (st[i] - cut + m) % m + 1;
        cout << a << " \n"[i + 1 == n];
    }
}

约定

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

#define int long long
#define pii array<int, 2>
#define endl "\n"

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout << fixed << setprecision(20);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i) {
        solve();
    }
    return 0;
}