记一次打表没看出规律
Time Limit: 5000/2500 MS (Java/Others)
There is a nonnegative integer sequence $ a_1…n$ of length $ n$. HazelFan wants to do a type of transformation called prefix-XOR, which means a1…n changes into b1…n, where bi equals to the $ XOR$ value of $ a_1,…,a_i$. He will repeat it for $ m$ times, please tell him the final sequence.

Input

The first line contains a positive integer $ T(1≤T≤5)$, denoting the number of test cases.
For each test case:
The first line contains two positive integers $ n,m(1≤n≤2×10^5,1≤m≤10^9)$.
The second line contains $ n $nonnegative integers $ a_1…n$ $ (0≤a_i≤2^30−1)$.

Output

For each test case:
A single line contains $n$ nonnegative integers, denoting the final sequence.

Sample Input

2
1 1
1
3 3
1 2 3

Sample Output

1
1 3 1

Source

2017 Multi-University Training Contest – Team 7

题解:

这里用到了卢卡斯定理的推论:对于$C_n^m$ 为奇数的充要条件是 $ n \& m == m$
对于变换m次我们考虑每个数的倒数k位数,打表看出倒数第k位数的系数为$ C_{k+m-2}^{k-1}$这样通过推论可以确定奇偶性,由异或性质可判断这个系数对应的数对每个数是否有贡献。另开一个数组$ b$,存贡献。遍历从$ 1~n$,在每次循环中得出倒数第$ i$位数对第$ i$ ~ $ n$个数是否有贡献。

Code:

#include<bits/stdc++.h>
using namespace std;
//打表找规律杨辉三角
inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x<em>10+ch-'0';ch=getchar();}
    return x*f;
}
const int maxn = 2e5+7;
int a[maxn],b[maxn];
int main() {
    int t = read();
    while(t--) {
        memset(b,0,sizeof(b));
        int n = read(), m = read();
        //对于第x次变换的第y个数,他的1~y的各项的系数为C(x+y-2,y-1)
        for(int i=1;i<=n;i++) a[i] = read();
        for(int i=1;i<=n;i++) {//对于第m次变换的倒数第i个数而言
            int mm = i-1, nn = i + m - 2;
            if((nn&mm)==mm) //每位数的倒数第i个数的二项式系数为奇数
                for(int j=i;j<=n;j++) b[j] ^= a[j-i+1];
        }
        for(int i=1;i<=n;i++)  printf("%d%c",b[i],i==n?'\n':' ');
    }
}
分类: 数论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.