HDU 6129 Just do it（杨辉三角）

http://acm.hdu.edu.cn/showproblem.php?pid=6129

题意：

给出数组a，并且bi=a1^a2^a3...^ai，并且现在会重复m次，求出最后的b数组。

思路：

简单的打个表，如果斜着看，可以发现a的系数就是杨辉三角。

这道题目需要知道的就是杨辉三角和组合数的关系，杨辉三角中第n行，m个元素的值就是$C(n-1,m-1)$，这里的话第x次变换时第y项的值就是$C(x+y-2,y-1)$。这样的话，我们就可以方便的计算出各个系数，并且判断一下奇偶，只有奇数才会有贡献。

那么怎么快速计算呢？观察第m行，可以发现：

这样一来先计算第1列的a1，然后后面几列的对应的数也就出来了，然后计算第二列的a1...这样的话就是做到了分块处理，如果系数是偶数，直接剪枝了不少循环，能大大的减少耗时。

像我一开始就有点傻了，先是计算a1对第m行所有的数的贡献，然后计算a2对m行的数的贡献...这样就很TLE了。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 const int maxn=2*1e5+5;
 7 
 8 int n, m;
 9 int a[maxn];
10 int b[maxn];
11 
12 int main()
13 {
14     //freopen("in.txt","r",stdin);
15     int T;
16     scanf("%d",&T);
17     while(T--)
18     {
19         memset(b,0,sizeof(b));
20         scanf("%d%d",&n,&m);
21         for(int i=1;i<=n;i++)  scanf("%d",&a[i]);
22 
23         /*  //一开始的思路，TLE了
24         for(int i=1;i<=n;i++)
25         {
26             for(int j=i;j<=n;j++)
27             {
28                 int y=j-i;
29                 int x=j-i+m-1;
30                 if((x&y)==y)
31                 {
32                     b[j]^=a[i];
33                 }
34             }
35         }
36         */
37         
38         for(int i=1;i<=n;i++)
39         {
40             int y=i-1;
41             int x=i+m-2;
42             if((x&y)==y)
43             {
44                 for(int j=i;j<=n;j++)
45                     b[j]^=a[j-i+1];
46             }
47         }
48 
49         for(int i=1;i<=n;i++)
50             printf("%d%c",b[i],i==n?'
':' ');
51     }
52     return 0;
53 }