把初始a的每一个元素对m次变换的贡献写出来，发现是一个斜着的杨辉三角，根据lucas，当且仅当a&b == b，C(a, b)为奇数，又因为&和^运算极快，4e10的复杂度也就跑了一秒。
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <vector> #include <string> #include <cmath> #include <map> using namespace std; const int maxn = 200005; int a[maxn], b[maxn]; int solve(int x, int y) { // cout << "x == " << x << " y == " << y << endl; if(x == 1) return a[y]; if(y == 1) return a[1]; int tmp = min(x, y); for(int i = 30; i >= 0; --i) if(tmp - (1 << i) > 0) { return solve(x - (1 << i), y) ^ solve(x, y - (1 << i)); } } int main() { // freopen("1010.in", "r", stdin); int T; scanf("%d", &T); while(T--) { int n, m; scanf("%d%d", &n, &m); for(int i = 1; i <= n; ++i) { scanf("%d", &a[i]); } memset(b, 0, sizeof(b)); for(int i = 0; i <= n - 1; ++i) { int y = m + i - 1, x = i; // cout << "x == " << x << " y == " << y << endl; if((x & y) == x) { for(int j = 1; j + i <= n; ++j) b[j + i] ^= a[j]; } } for(int i = 1; i <= n; ++i) { if(i != 1) printf(" "); printf("%d", b[i]); } printf("\n"); } }
原文：http://www.cnblogs.com/Rhantolk/p/7374571.html
