HDU 6129 Just do it

　　题意：给你一个包含n个数的序列A和一个数m，序列B中的数是序列A经过异或得到的，比如：b[i]=a[1]^a[2]^…..^a[i]。现在让你求经过m次异或后，序列B的值。

　思路：这题其实和杨辉三角形有关。

　首先我们打个表可以得到

　　我们知道杨辉三角形

　　我们可以看到一个规律，我们单独把a提出来，每一行便是

　　我们斜着看杨辉三角形

　　可以发现是相等的，我们就得到结论(i,j)位置的数值等于C(i+j-2, j-1)，判断此处的奇偶便好。

/** @xigua */

#include <cstdio>

#include <cmath>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <cstring>

#include <queue>

#include <set>

#include <string>

#include <map>

#include <climits>

#define PI acos(-1)

using namespace std;

typedef long long ll;

typedef double db;

const int maxn = 2e5 + ;

const int mod = 1e9 + ;

const int INF = 1e8 + ;

const ll inf = 1e15 + ;

const db eps = 1e-;

int a[maxn], b[maxn];

void solve() {

    int n, m;  scanf("%d%d", &n, &m);

    memset(b, , sizeof(b));

    memset(a, , sizeof(a));

    for (int i=; i<=n; i++)  scanf("%d", &a[i]);

    for (int i=; i<=n; i++) {

        int x=i+m-, y=i-;

        if ((x&y)==y) {　　//判断奇偶

            for (int j=i; j<=n; j++)

                b[j]^=a[j-i+];

        }

    }

    for (int i=; i<=n; i++) {

        if (i-)  printf(" ");

        printf("%d", b[i]);

    }

    puts("");

}

int main() {

    int t = , cas = ;

    //freopen("in.txt", "r", stdin);

   // freopen("out.txt", "w", stdout);

    scanf("%d", &t);

    while(t--) {

       // printf("Case %d: ", cas++);

        solve();

    }

    return ;

}

巴特西

HDU 6129 Just do it

最新文章

热门文章