\(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个小时）
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;
}