HDU-6129 Just do it - 2017 Multi-University Training Contest - Team 7(規律、楊輝三角、組合數奇偶性)

題意：

設b[i] = a[1]^a[2]^a[3]^..................a[i]；

每進行一次，a數組會變成一個b數組。問進行m次的結果。

思路：

寫出前幾項的前幾次結果，結果以每個元素的及其用到的個數顯示。然後把a[1]的個數抽象出來，會發現是一個斜着的楊輝三角，a[2]則是a[1]的楊輝三角整體向右移一位。是以我們就能得到第m行第j列的元素a[1]的系數是C(m+j-2, j-1)。

然後再通過觀察第m行其它列的各個元素的系數，會發現從目前列中元素a[1]的系數，等于下一列的a[2]的系數，等于下下一列的a[3]的系數...

之後需要根據Lucas定理的推廣快速判斷一個組合數值的奇偶性，其實就是一個式子(n&m) == m?是為奇否為偶。也可以用代碼中的方法。

代碼：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
int a[maxn], b[maxn];
int isodd(int n, int m)
{
	while(m)
	{
		if((m&1) && !(n&1)) return 0;
		m >>= 1, n >>= 1;
	}
	return 1;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	int n, m, t;
	scanf("%d", &t);
	while(t--)
	{
		scanf("%d %d", &n, &m);
		memset(b, 0, sizeof b);
		for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
		for(int i = 1; i <= n; ++i)
		{
			if(isodd(m+i-2, i-1))
			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':' ');
	}
	return 0;
}
           

繼續加油~