设定b【i】=a【1】^a【2】^a【3】^………………a【i】；
每进行一次，我们可以从a数组得到一个b数组。问进行m次的结果。
我们把前几轮的结果都写出来;
会发现,最后每一个位置ai的结果都是
t1@a1+t2@a2+…+ti@ai的形式.
这里的x@y表示x个y做异或运算.
t1是系数,它>=0
且最后的ai的系数,是a[i+1]的后i项系数.
也就是说只要我们把an的t1到tn求出来就好了;
会发现有a[i][j] = a[i][j-1]+a[i-1][j]的规律..
这样就能打一张大表了
然后就是找规律了。。
在OEIS上发现。。
第i列就是C(i+m-2,i-1);
则t1..tn都能求出来了
我们不用知道这一项具体是什么;
只希望知道它的奇偶性就好。
(奇数就为1,否则为0);
有个结论.
当(n&m) == m的时候,C(n,m)的值才为奇数
这样就能根据t1..tn算出an了;
再根据最后的ai的系数,是a[i+1]的后i项系数进而可以算出a1..an-1
这里我只记录了ti为1的位置,且在做的时候把没用的位置删掉了.
这样避免了O(n^2)的复杂度.
因为当(n&m) == m的时候,C(n,m)的值才为奇数,可以想见最后系数为1的值是挺少的
1
(PE了一发,注意行末空格啊！！)
OEIS帮了大忙.
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ll long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define ri(x) scanf("%d",&x)
#define rl(x) scanf("%lld",&x)
#define rs(x) scanf("%s",x+1)
#define oi(x) printf("%d",x)
#define ol(x) printf("%lld",x)
#define oc putchar(' ')
#define os(x) printf(x)
#define all(x) x.begin(),x.end()
#define open() freopen("f:\rush.txt","r",stdin)
#define close() ios::sync_with_stdio(0)
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 2e5;
int a[N+100],t,n,m,b[N+100];
vector <int> v;
int c(int n,int m){
if ( (n&m) == m)
return 1;
else
return 0;
}
int main(){
//open();
//close();
ri(t);
while (t--){
ri(n),ri(m);
rep1(i,1,n) ri(a[i]);
v.clear();
for (int i = 1,j = n;i <= n;i++,j--){
int b;
if (i == 1)
b = 1;
else
if (i == 2) b = m&1;
else
if (i == 3) b = c(m+1,2);
else
if (i == 4) b = c(m+2,3);
else
b = c(m+i-2,i-1);
if (b==1) v.pb(j);
}
rep2(i,n,1){
while ( (int) v.size()){
int k = v.back();
if (k-(n-i)<=0) {
v.pop_back();
continue;
}
break;
}
int len = v.size();
int temp = 0;
rep1(k,0,len-1){
int key = v[k];
int j = key -(n-i);
temp^=a[j];
}
b[i] = temp;
}
rep1(i,1,n) {
oi(b[i]);
if (i == n)
puts("");
else
oc;
}
}
return 0;
}