hdu6129

201708

• 现场没想到这个式子是可以这样变形的
  
  • $f_{i,j} = f_{i-1,j} xor f_{i,j-1}$
  • $f_{i,j} = f_{i-2,j} xor f_{i,j-2}$
  • $f_{i,j} = f_{i-2^k,j} xor f_{i,j-2^k}$
• 再结合一下一开始找到的循环节，观察一下图感觉是可以推出来的
• 现场一直在推杨辉三角，走远了

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define mp make_pair
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define de(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
//--------
const int N=200005;
int n,m;
int a[N];
int main() {
    int T;scanf("%d",&T);
    while(T--) {
        scanf("%d%d",&n,&m);
        rep(i,1,n+1) scanf("%d",a+i);
        for(int i=30;i>=0;--i) {
            if(m&(1<<i)) {
                rep(j,(1<<i)+1,n+1) {
                    a[j]=a[j-(1<<i)]^a[j];
                }
            }
        }
        rep(i,1,n+1) printf("%d%c",a[i],(i==n)?'\n':' ');
    }
    return 0;
}