codeforces C. Magic Formulas 解题报告

题目链接：http://codeforces.com/problemset/problem/424/C

题目意思：给出 n 个数：p1, p2, ..., pn，定义：

q1 = p1 ^ (1 mod 1) ^ (1 mod 2) ^ (1 mod 3) ...^(1 mod n)；

q2 = p2 ^ (2 mod 1) ^ (2 mod 2) ^ (2 mod 3) ...^(2 mod n)；

...

qn = p3 ^ (n mod 1) ^ (n mod 2) ^ (n mod 3) ...^(n mod n)

Q = q1 ^ q2 ...^ qn

要求算出 Q

很明显，如果直接做绝对是超时的。在这里，非常感谢 yk 师弟不厌其烦地为我解释思路，虽然最后我并没有按他的思路做......

那么，不能直接算就需要从公式中找规律。首先要清楚的是，异或 ^ 运算满足交换律；所以可以先求出 p1 ^ p2 ^ ...^ pn，并且可以先求出第一列异或的结果，再跟第二列求出的异或结果异或...直到跟最后一列的结果异或。其次，假设 n 代表一个非零整数，有3条公式需要知道：（1）0 ^ n = n；（2）n ^ n = 0（可以推广到异或偶数次自身），（3） n ^ n ^ n = n（可以推广到异或奇数次自身）。这3个公式对后面的的计算进行简化。

假设n = 5。接着请读者打竖看，即 1 mod 1, 2 mod 1， ...， 7 mod 1 地看。很明显这一列异或之后是等于0的！那么从第二列开始看：第三列第四列第五列

1 mod 2 = 1 1 mod 3 = 1 1 mod 4 = 1 1 mod 5 = 1

2 mod 2 = 0　　　　　　　　　　 2 mod 3 = 2 2 mod 4 = 2 2 mod 5 = 2

3 mod 2 = 1 3 mod 3 = 0 3 mod 4 = 3 3 mod 5 = 3

4 mod 2 = 0 4 mod 3 = 1　　　　　　4 mod 4 = 0 4 mod 5 = 4

5 mod 2 = 1 5 mod 3 = 2 5 mod 4 = 1 5 mod 5 = 0

观察这些数，可以得出每一列 mod 出来的结果都是比被 mod 数小的：第二列 mod 出来的结果都比 2 小；第三列 mod 出来的结果都比 3 小；...第五列比 5 小。再观察发现，每一列 mod 出来的数是有周期性的。这时需要用到上面所说的后两条公式了。需要知道这些周期究竟是计数还是偶数，如果是偶数，相当于根本没有做过异或操作；否则异或一次。周期数的计算可以用这个公式 (n-n%i)/i 求出。最后要处理的是最后面的那些不成周期的数究竟是什么，可以用到 n % i 来得出。（i 表示每列中被mod的数）

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 const int maxn = 1e6;

 int num[maxn];

 int main()

 {

     int i, p, n, ans;

     num[] = ;

     for (i = ; i <= maxn; i++)

         num[i] = num[i-] ^ i;   // num[1] = 0^1; num[2] = 0^1^2; num[n] = 0^1^2...^n

     while (scanf("%d", &n) != EOF)

     {

         ans = ;

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

         {

             scanf("%d", &p);

             ans ^= p;    // 先求出p1^p2^...^pn

         }

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

         {

             int tmp = n - n % i;

             if ((tmp/i) & )      // tmp/i 表示有多少个周期数

                 ans ^= num[i-];

             ans ^= num[n%i];     // 不成周期数的独立处理

         }

         printf("%d\n", ans);

     }

     return ;

 }

巴特西

codeforces C. Magic Formulas 解题报告

最新文章

热门文章