( ext{Description})
( ext{Solution})
我们考虑每个 (a_i) 对之后的数的影响（注意这里的影响是影响次数）。
图片转自 protecteyesight。
令这个矩阵为 (b)，对于 (b[i][j])，(b[i-1][j]) 表示的是上一轮的 (a_j)，(b[i][j-1]) 是这一轮已经求出的 (sum_{k=1}^{j-1} a_k)。
所以得出式子：(b[i][j]=b[i-1][j]+b[i][j-1])。
法一
我们单纯地看 (a_1)。很明显矩阵关于 (a_1) 项的系数是一个向左斜的杨辉三角（其实由递推式即可得出），坐标 ((i,j)) 的系数就是 ( ext C(i+j-2,j-1))。
同理其它 (a) 都有各自的杨辉三角，只是相较于 (a_1) 的规模小了一点。
我们可以枚举杨辉三角的 (j)（相同系数与每个杨辉三角的零点距离相等），如果为奇就异或上去（当 (n & m=m, ext C(n,m)) 为奇）。
法二
我们将 (b) 数组模 (2) 来运算（相当于又转成异或）。
你会发现：
[b[i][j]=b[i-1][j]+b[i][j-1]
]
[=b[i-2][j]+b[i][j-2]+2b[i-1][j-1]
]
[=b[i-2^k][j]+b[i][j-2^k]
]
这实际上就是 ( ext{C}(2^k,i)) 在 (iin (0,2^k)) 时恒为偶数。
( ext{Code})
法一
#include <cstdio>
#define rep(i,_l,_r) for(register signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(register signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
template <class T> inline T Max(const T x,const T y) {if(x>y) return x; return y;}
template <class T> inline T Min(const T x,const T y) {if(x<y) return x; return y;}
template <class T> inline T fab(const T x) {return x>0?x:-x;}
template <class T> inline T gcd(const T x,const T y) {return y?gcd(y,x%y):x;}
template <class T> inline T lcm(const T x,const T y) {return x/gcd(x,y)*y;}
template <class T> inline T Swap(T &x,T &y) {x^=y^=x^=y;}
#include <cstring>
const int maxn=2e5+5;
int a[maxn],b[maxn],n,m,N,M;
int main() {
for(int t=read(9);t;--t) {
memset(b,0,sizeof b);
n=read(9),m=read(9);
rep(i,1,n) a[i]=read(9);
rep(i,1,n) {
N=m+i-2; M=i-1;
if((N&M)==M)
for(int j=i;j<=n;++j)
b[j]^=a[j-i+1];
}
rep(i,1,n-1) print(b[i],' ');
print(b[n],'
');
}
return 0;
}
法二
代码转自 Just_JK。
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
using namespace std;
const int N = 2e5+5;
int dp[N];
int main() {
int T;
scanf("%d", &T);
while(T--) {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i++) scanf("%d", &dp[i]);
while(m) {
int x = m&-m; // x 枚举了 2^k
for(int j = x; j < n; j++) {
dp[j] ^= dp[j-x]; // dp[j](sum状态)=dp[j](sum-x状态,即上一个循环sum的状态)^dp[j-x](sum状态)
}
m -= x;
}
for(int i=0;i<n;i++)
{
if(i!=n-1)
printf("%d ",dp[i]);
else
printf("%d
",dp[i]);
}
}
return 0;
}