情报破译 题解

\(d<n\le 2e5,m\le 10,1\le p\le 10^9,0\le a_i\le 1e9\)

每个位运算之间独立，所以我们可以构造一个

\(\{2^{k-1},2^{k-1}.....\}\)

和一个

\(\{0,0,0...\}\)

的数组，让他们倍增去做如上运算，最后用他们把 \(p\) 轮拼出来，我们就知道了 \(i\) 位置上二进制下第 \(j\) 位如果是 \(0\) ，最后会变成什么，反之亦然。

设\(F_{i,j}\)表示i位置 \(full(2^k-1)\) 做了\(2^j\)轮以后的情况

\(G_{i,j}\)表示i位置 \(zero(0)\) 做了\(2^j\)轮以后的情况

转移为

\(F_{i,j}=(F_{i,j-1} \& F_{i+2^{j-1}*(m*d),j-1})|((\sim F_{i,j-1})\&(G_{i+2^{j-1}*(m*d),j-1}))\)

分别表示位置为1再做\(2^{j-1}\)会变成什么和为0位置再做\(2^{j-1}\)会变成什么

G转移同理，两者互相转移

Tip：拼 \(p\) 时别忘了位移数组，记录已经做的轮数（调了1个小时）

时间复杂度：\(O(nm+n\log V)\)

code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fr first
#define sc second
inline int rd() {
    int res = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        res = res * 10 + (ch - '0');
        ch = getchar();
    }
    return res * f;
}
const int N = 2e5 + 10;
int n, m, d, p, mx;
int b[N], full;
char opt[N][3];
deque<int> now;
int f[N][36], g[N][36], a1[N], a0[N];
signed main() {
    // freopen("A.in", "r", stdin);
    // freopen("A.out", "w", stdout);
    n = rd();
    m = rd();
    d = rd();
    p = rd();
    for (int i = 0; i < n; i++) {
        b[i] = rd();
        mx = max(mx, __lg(b[i]) + 1);
        now.push_back(b[i]);
    }
    full = (1ll << 35) - 1;
    for (int i = 1; i <= m; i++)
        scanf("%s", opt[i]);
    for (int i = 0; i < n; i++)
        f[i][0] = full;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j < d; j++) {
            now.push_back(now.front());
            now.pop_front();
        }
        for (int j = 0; j < n; j++) {
            if (opt[i][0] == 'x')
                f[j][0] ^= now[j], g[j][0] ^= now[j];
            else if (opt[i][0] == 'a')
                f[j][0] &= now[j], g[j][0] &= now[j];
            else if (opt[i][0] == 'o')
                f[j][0] |= now[j], g[j][0] |= now[j];
        }
    }
    for (int j = 1; j <= 35; j++) {
        for (int i = 0; i < n; i++) {
            f[i][j] =
                (f[i][j - 1] &
                 f[(i + (1ll << (j - 1)) % n * m % n * d % n) % n][j - 1]) |
                ((full ^ f[i][j - 1]) &
                 g[(i + (1ll << (j - 1)) % n * m % n * d % n) % n][j - 1]);
            g[i][j] =
                ((full ^ g[i][j - 1]) &
                 g[(i + (1ll << (j - 1)) % n * m % n * d % n) % n][j - 1]) |
                (g[i][j - 1] &
                 f[(i + (1ll << (j - 1)) % n * m % n * d % n) % n][j - 1]);
        }
    }
    for (int i = 0; i < n; i++)
        a1[i] = full;
    int res = 0;
    for (int i = 0; (1ll << i) <= p; i++) {
        if ((p >> i) & 1) {
            for (int j = 0; j < n; j++) {
                a1[j] = (a1[j] & f[(j + res * d % n * m % n) % n][i]) |
                        ((full ^ a1[j]) & g[(j + res * d % n * m % n) % n][i]);
                a0[j] = (a0[j] & f[(j + res * d % n * m % n) % n][i]) |
                        ((full ^ a0[j]) & g[(j + res * d % n * m % n) % n][i]);
            }
            res |= (1ll << i);
            res %= n;
        }
    }
    // for (int i = 0; i < n; i++) {
    // for (int j = 0; j < 3; j++)
    // printf("%lld", (a1[i] >> j) & 1);
    // puts("");
    // }
    for (int i = 0; i < n; i++) {
        int res = 0;
        for (int j = 0; j <= 35; j++) {
            if ((b[i] >> j) & 1)
                res |= (((a1[i] >> j) & 1) << j);
            else
                res |= (((a0[i] >> j) & 1) << j);
        }
        printf("%lld ", res);
    }
    return 0;
}