hdu6129 Just Do It！

多校时找规律做过。。。

题意，给你一个数列a[1], a[2], a[3], a[4], ... , a[n]，操作一次后变为a[1], a[1] ^ a[2], a[1] ^ a[2] ^ a[3], ..., a[1] ^ a[2] ^ a[3] ^...^a[n]，

让你计算出m次操作后的数列

令F(x, y, i) 表示x次操作后新的a[y]中初始 a[i]被亦或的次数

F(x, y, i) = F(x - 1, y, i) + F(x, y - 1, i)

联系几何意义，实际就是(1, i) 到 (x, y) 的路径条数，即 C(m - 1 + x - i, x - i)。

即可得到n^2的做法，猜想这些组合数中偶数很多，调整循环顺序，就AC了

这里判断组合数是否为偶数，采用了比较2的方幂的方法。

当然，也可以使用库摩尔定理(大概是15年联赛数论23333)

库摩尔定理：有两个正整数n,m，p是质数，C(n + m, m) 含ｐ的幂次等于ｍ＋ｎ在ｐ进制下的进位数。

(在p进制下，产生一次进位，会贡献一个p)

当p为2时，若C(n + m, m)为奇数，则m+n不能产生进位，则意味着m数位为1的地方n必须为0，n数位为1的地方m必须为0，即 m & n = 0

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int N = 2e5 + ;

int a[N], b[N];

#define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i) 

inline int f(int x) {

    int ret = ;

    while (x) {

        ret += (x >> );

        x >>= ;

    }

    return ret;

}

inline int Comb(int n, int m) {

    return f(n) - f(m) - f(n - m);

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) {

        int n, m;

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

        rep(i, , n) scanf("%d", a + i);

        // rep(x, 1, n) {

        //     rep(i, 1, x) {

        //         if (!Comb(m  - 1 + x - i, x - i)) b[x] ^= a[i];

        //     }

        // }

        rep(j, , n - )

        if (!Comb(m -  + j, j)) {

            rep(x, j + , n) {

                int i = x - j;

                b[x] ^= a[i];

            }

        }

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

        printf("%d\n", b[n]);

        memset(b, , sizeof(b));

    }

}

巴特西

hdu6129 Just Do It！

最新文章

热门文章