wordpress获取当前页地址/seo博客写作

Description

给出一个序列$a_{1,2,...,n}$，每次操作对该序列求一遍异或前缀和，问$m$次操作后的序列

Input

第一行一整数$T$表示用例组数，每组用例首先输入两个整数$n$和$m$分别表示序列长度和操作数，之后输入$n$个整数$a_{1,2,...,n}$$(1\le T\le 5,1\le n\le 2\cdot 10^5,1\le m\le 10^9,0\le a_i\le 2^{30}-1)$

Output

输出$m$次操作后的序列

Sample Input

2
1 1
1
3 3
1 2 3

Sample Output

1
1 3 1

Solution

设$m$次操作后的序列为$b_{1,2,...,n}$，类似杨辉三角知$a_i$对$b_j$的贡献为$C_{m-1+j-i}^{j-i}$，而使得$C_{m-1+k}^k$为奇数的$k$并不多，故可以枚举$k$，如果$C_{m-1+k}^k$为奇数则枚举$i$，$a_i$对$b_{i+k}$有贡献

注：$C_n^m$为奇数当且仅当$n\&m=m$

Code

#include<cstdio>
using namespace std;
typedef long long ll;
#define maxn 200005
int T,n,m,a[maxn],ans[maxn];
int C(int n,int m)
{if((n&m)==m)return 1;return 0;
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d",&a[i]),ans[i]=a[i];for(int i=1;i<n;i++)if(C(m+i-1,i))for(int j=0;j+i<n;j++)ans[j+i]^=a[j];for(int i=0;i<n;i++)printf("%d%c",ans[i],i==n-1?'\n':' ');}return 0;
}