比赛链接

C

题解

知识点：位运算，贪心。

我们用分段的思想考虑大小关系，若在同一段则大小不能确定，一开始为 $[1,n]$ 。

我们按位从高到低考虑，某位如果 $b_i$ 产生了 $1$ ，那么会这一位的第 $i$ 个数产生大小的分段，得到 $[1,i-1]<[i,n]$ ，之后这两段的大小关系就确定了，我们可以对各段分别继续相同的讨论。

同时，若在某一位，某段中产生分段，在这段的分段点之前所有数字的这一位一定是全 $0$ ，之后一定是全 $1$ ，否则就会大小关系矛盾无解。因此，分段后 $0,1$ 的情况就立刻确定了。此时可能会出现，在某一位，之前产生的分段已经限制了当前位的情况，而当前的分段需要的 $0,1$ 情况和之前确定的不同，此时也无解。

到最后，我们确定了所有能确定的位，剩下的位就是自由的。我们发现只要确定 $a_1$ 即可确定所有数字，我们用 $k-1$ 的二进制，从低位到高位填入 $a_1$ 的自由位，就可以得到字典序第 $k$ 小的序列。

实现时，我们对 $b$ 数组前缀异或和，此时得到的是每一个数字和 $a_1$ 异或的值，用刚才的思路稍作修改，即可直接完成对 $a_1$ 每一位情况的确定。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int a[1000007];int a1[30];bool solve() {    int n, k;    cin >> n >> k;    a[1] = 0;    for (int i = 2;i <= n;i++) cin >> a[i], a[i] ^= a[i - 1];     vector<pair<int, int>> seg = { {1,n} };    for (int i = 29;i >= 0;i--) {        vector<pair<int, int>> tmp;        a1[i] = -1;        for (auto [l, r] : seg) {            int pos = l;            while (pos <= r) {                if ((a[l] >> i & 1) != (a[pos] >> i & 1)) break;                pos++;            }            tmp.push_back({ l,pos - 1 });            if (pos > r) continue;            tmp.push_back({ pos,r });            for (int j = pos;j <= r;j++) {                if ((a[pos] >> i & 1) == (a[j] >> i & 1)) continue;                return false;            }            int x = a[l] >> i & 1;            if (a1[i] != -1 && a1[i] != x) return false;            a1[i] = x;        }        seg = tmp;    }     k--;    for (int i = 0;i <= 29;i++) {        if (a1[i] != -1) a[1] |= a1[i] << i;        else {            a[1] |= (k & 1) << i;            k >>= 1;        }    }    if (k) return false;    for (int i = 1;i <= n;i++) cout << (i == 1 ? a[1] : a[1] ^ a[i]) << " \n"[i == n];    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

G

题解

知识点：模拟，数学。

注意到，我们可以把能互相修改的环单独拿出来考虑，考虑每个环是否可以清零即可。

对于一个环 $a_1,a_2,\cdots,a_m$，我们随意选择一个数字作为起点，假设将其和下一个环上相邻的数字 $a_2$ 减去 $x$ ，再将后续数字清零并回到 $a_1$ 将 $a_1$ 清零，呈现操作次数为 $x,a_2 - x,a_3-a_2 + x, \cdots$ 。最后一步，得到的是将 $a_1$ 清零的操作次数，它应该等于 $x$ 。

在这个过程中，我们利用操作次数必须是非负的，来收紧 $x$ 的上下界 $[l,r]$ ，若上下界是空集，则无解。

我们发现操作次数是个一次函数，若 $m$ 是奇数则得到 $-x+b$ ，否则为 $x + b$ 。对于前者情况，若 $b$ 是偶数则 $x = b/2$ ，否则无解；对于后者情况，若 $b \neq 0$ 则 $x$ 在 $[l,r]$ 范围任意有解，否则无解。

时间复杂度 $O(n)$

空间复杂度 $O(n)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; int a[1000007];bool vis[1000007]; bool check(const vector<int> &cyc) {    int sz = cyc.size();    ll val = 0;    ll l = 0, r = cyc[0];    for (int i = 1;i <= sz;i++) {        val = cyc[i % sz] - val;        if (i & 1) r = min(r, val);        else l = max(l, -val);    }    if (r < l) return false;    if (sz & 1) {        if (val & 1) return false;        ll x = val / 2;        if (x < l || x > r) return false;        return true;    }    else return val == 0;} bool solve() {    int n, k;    cin >> n >> k;    bool ok = 1;    for (int i = 0;i < n;i++) cin >> a[i], vis[i] = 0, ok &= !a[i];    if (ok) {        cout << "YES" << '\n';        return true;    }    else if (k > n / 2) {        cout << "NO" << '\n';        return true;    }    for (int i = 0;i < n;i++) {        if (vis[i]) continue;        vector<int> cyc;        int pos = i;        while (!vis[pos]) {            cyc.push_back(a[pos]);            vis[pos] = 1;            (pos += k) %= n;        }        if (!check(cyc)) {            cout << "NO" << '\n';            return true;        }    }    cout << "YES" << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}

I

题解

知识点：根号分治，容斥原理，枚举。

先将字符串按长度分类。

对于同一个长度的字符串，考虑按长度和个数分治，若长度大于个数则用字符串本身容斥，否则直接暴力搜索每个可能的串并检查是否能匹配。

后者情况很好处理，前者的容斥每次需要选择一个字符串的子集，计算子集中字符串的共同贡献。因此，对于一个子集里的字符串，每一位都必须是不矛盾的，否则这个子集的贡献是 $0$ ，最后统计有多少位置是自由的，即可计算贡献。

时间复杂度 $O(2^{\sqrt{n}} \sum |s_i|)$

空间复杂度 $O(\sum |s_i|)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; const int P = 998244353; vector<string> s[407];int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n;    cin >> n;    for (int i = 1;i <= n;i++) {        string t;        cin >> t;        s[t.size()].push_back(t);    }     int ans = 0;    for (int i = 1;i <= 400;i++) {        if (!s[i].size()) continue;        if (s[i].size() > i) {            for (int j = 0;j < (1 << i);j++) {                for (auto str : s[i]) {                    bool ok = 1;                    for (int k = 0;k < i;k++) ok &= str[k] == '?' || (j >> (i - k - 1) & 1) == str[k] - '0';                    if (ok) {                        (ans += 1) %= P;                        break;                    }                }            }        }        else {            int sz = s[i].size();            for (int j = 1;j < (1 << sz);j++) {                bool f = 0;                string tmp(i, '?');                for (int k = 0;k < sz;k++) {                    if (!(j >> k & 1)) continue;                    f ^= 1;                    for (int l = 0;l < i;l++) {                        if (s[i][k][l] == '?') continue;                        if (tmp[l] == '?') tmp[l] = s[i][k][l];                        if (tmp[l] != s[i][k][l]) tmp[l] = '#';                    }                }                 int mul = 1;                bool ok = 1;                for (int k = 0;k < i;k++) {                    mul = (tmp[k] == '?' ? 2LL : 1LL) * mul % P;                    ok &= tmp[k] != '#';                }                if (ok) (ans += (f ? 1 : -1) * mul) %= P;            }        }    }     cout << ans << '\n';    return 0;}

L

题解

知识点：KMP。

对于 $|s| > |t|$ 时，显然答案是 $0$ ，否则暴力跑一次KMP即可，时间复杂度是 $|t|$ 的总和。

时间复杂度 $O(\sum |t|)$

空间复杂度 $O(|s| + |t|)$

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; template<class T>class KMP {    int m;    T p; public:    vector<int> nxt;     KMP() {}    KMP(const T &_p) { init(_p); }     void init(const T &_p) {        m = _p.size() - 1;        p = _p;        nxt.assign(m + 1, 0);        for (int i = 2;i <= m;i++) {            nxt[i] = nxt[i - 1];            while (nxt[i] && p[i] != p[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];            nxt[i] += p[i] == p[nxt[i] + 1];        }    }     vector<int> find(const T &s) {        int n = s.size() - 1;        vector<int> pos;        for (int i = 1, j = 0;i <= n;i++) {            while (j && s[i] != p[j + 1]) j = nxt[j];            j += s[i] == p[j + 1];            if (j == m) {                pos.push_back(i - j + 1);                j = nxt[j];            }        }        return pos;    }     vector<int> get_cycle_time() {        vector<int> res;        int pos = m;        while (pos) {            pos = nxt[pos];            res.push_back(m - pos);        }        return res;    }     vector<int> get_cycle_loop() {        vector<int> res;        for (auto val : get_cycle_time())            if (!(m % val)) res.push_back(val);        return res;    }    int min_cycle_loop() { return get_cycle_loop()[0]; }     void debug() {        for (int i = 1;i <= m;i++)            cout << nxt[i] << " \n"[i == m];    }};/// KMP，前缀函数O(|P|)、查找O(|S|+|P|)、循环相关O(|P|)，维护字符串前缀函数 int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int n, q, b, p;    cin >> n >> q >> b >> p;     vector<int> s(n + 1);    for (int i = 1;i <= n;i++) cin >> s[i];     ll z = 0;    int mul = 1, ans = 0;    while (q--) {        int op;        cin >> op;        if (op == 1) {            ll x, c;            cin >> x >> c;            x = (x ^ z) % n + 1;            c ^= z;            s[x] = c;        }        else {            int m;            cin >> m;            vector<int> t(m + 1);            for (int i = 1;i <= m;i++) {                ll val;                cin >> val;                t[i] = val ^ z;            }            mul = 1LL * mul * b % p;            if (m < n) z = 0;            else {                KMP<vector<int>> kmp(s);                z = 1LL * kmp.nxt[n] * kmp.find(t).size();            }            ans = (ans + z % p * mul % p) % p;        }    }    cout << ans << '\n';    return 0;}

M

题解

知识点：数学。

枚举数字个数的范围即可。

代码

#include <bits/stdc++.h>using namespace std;using ll = long long; bool solve() {    int n;    cin >> n;    ll base = 10, cnt = 1;    ll ans = 0;    while (base - 1 <= n) {        ans += (base - base / 10) * cnt;        base *= 10;        cnt++;    }    base /= 10;    ans += (n - base + 1) * cnt;    cout << ans << '\n';    return true;} int main() {    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);    int t = 1;    cin >> t;    while (t--) {        if (!solve()) cout << -1 << '\n';    }    return 0;}