hdu--6129--Just do it

落日映苍穹つ 2022-06-10 13:36 101阅读 0赞

# Just do it #

**Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 524288/524288 K (Java/Others)  
Total Submission(s): 1228    Accepted Submission(s): 720**

Problem Description

There is a nonnegative integer sequence   a1...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   a1,...,ai. 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×105,1≤m≤109).  
The second line contains   n nonnegative integers   a1...n(0≤ai≤230−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

题意：

给出数组a，和整数m，求出数组a按照b\[i\]=a\[1\]^a\[2\]^....^a\[i\]，所有的b\[i\]更新完之后，b\[i\]变成新的a\[i\]，重复m次。

解题思路：

做这一题首先需要明确的是，某个数如果异或了偶次，就相当于没有异或，如果异或了奇数次，就相当于只异或了一次（因为异或偶数次，就相互抵消了）

接下来就只需要算每个数 对要求的数的贡献是奇数次还是偶数次就行了，在纸上写一些，找一下规律（拿第一个数的贡献为例，后面的可以类比）：

一 a            b                  c                                   d

二 a            a^b              a^b^c                         a^b^c^d

三 a            a^a^b         a^a^a^b^b^c            a^a^a^a^b^b^b^c^c^d

通过上面可以看出，a对各项的贡献为：

第一次 1 0 0 0 0   
第二次 1 1 1 1 1   
第三次 1 2 3 4 5   
第四次 1 3 6 10 15

发现，第一个数对后面的数的贡献数是一个杨辉三角，那么就可以推出：a对第x次变换第y项的贡献是C（x+y-2，y-1）次；后面的同样也是杨辉三角（这里不一 一例举），因为是杨辉三角，所以第一个数对第2个数如果是奇数次异或，那么第二个数对第三个数也是奇数次异或，后面的情况同理。c\[m\]\[n\]为奇数的判断条件为n&m==m(具体为啥，我也不知道.....)，这些都明白后，就只剩下写代码了：

代码：

C++ Code

<table style="width:100%; font-family:'Consolas','Courier New'; font-size:12px; vertical-align:text-top; line-height:15px"> 
 <tbody> 
 <tr> 
 <td style="color:#008284; background-color:#e3e3e3; vertical-align:text-top"> 
 <div style="margin:7px; text-align:right; white-space:nowrap">
 1 
 2 
 3 
 4 
 5 
 6 
 7 
 8 
 9 
 10 
 11 
 12 
 13 
 14 
 15 
 16 
 17 
 18 
 19 
 20 
 21 
 22 
 23 
 24 
 25 
 26 
 27 
 28 
 29 
 30 
 31 
 32 
 33 
 
 </div> </td> 
 <td style="background-color:#008284; padding:1px"> 
 <div style="border:1px #008284 solid"></div> </td> 
 <td style="background-color:rgb(239,239,239); width:100%; vertical-align:text-top"> 
 <div style="margin:7px"> 
 #include&nbsp;&lt;bits/stdc++.h&gt; 
 
 using&nbsp; 
 namespace&nbsp;std; 
 
 const&nbsp; 
 int&nbsp;maxn&nbsp;=&nbsp;2e5&nbsp;+&nbsp; 
 10; 
 
 long&nbsp; 
 long&nbsp;&nbsp;a[maxn]; 
 
 long&nbsp; 
 long&nbsp;&nbsp;b[maxn]; 
 
 int&nbsp;main() 
 { 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;T; 
 &nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;T; 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 while(T--) 
 &nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;memset(b,&nbsp; 
 0,&nbsp; 
 sizeof(b)); 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;n,&nbsp;m; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;n&nbsp;&gt;&gt;&nbsp;m; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cin&nbsp;&gt;&gt;&nbsp;a[i]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;=&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;x&nbsp;=&nbsp;i&nbsp;+&nbsp;m&nbsp;-&nbsp; 
 2; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 int&nbsp;y&nbsp;=&nbsp;i&nbsp;-&nbsp; 
 1; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 if((x&nbsp;&amp;&nbsp;y)&nbsp;==&nbsp;y) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;j&nbsp;=&nbsp;i;&nbsp;j&nbsp;&lt;=&nbsp;n;&nbsp;j++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;b[j]&nbsp;^=&nbsp;a[j&nbsp;-&nbsp;i&nbsp;+&nbsp; 
 1]; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
 for( 
 int&nbsp;i&nbsp;=&nbsp; 
 1;&nbsp;i&nbsp;&lt;&nbsp;n;&nbsp;i++) 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;b[i]&nbsp;&lt;&lt;&nbsp; 
 '&nbsp;'; 
 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;cout&nbsp;&lt;&lt;&nbsp;b[n]&nbsp;&lt;&lt;&nbsp;endl; 
 &nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;&nbsp; 
 return&nbsp; 
 0; 
 } 
 </div> </td> 
 </tr> 
 </tbody> 
</table>