TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3678
  • Problem
  • P3678异或序列
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

    有一个长度为n的整数序列S,已知S1=0。序列的其余元素可通过下列公式算出:Si=(Si-1*k+v)%d

    请你求出所有(Si+Sj)异或起来的结果(1<=i,j<=n)。
    即是求(S1+S1) xor (S1+S2) xor (S1+S3) xor...xor (S1+Sn) xor (S2+S1) xor (S2+S2) xor (S2+S3) xor...xor (S2+Sn) xor...xor (Sn+Sn)

    xor表示"异或",即c++中的"^"
    Input Format

    一行,四个整数,分别表示n,k,v,d

    Output Format

    一行,一个整数,表示所求结果。

    Sample Input 1

    3 7 2 6

    Sample Output 1

    12

    Sample Input 2

    5 8 3 7

    Sample Output 2

    4

    Sample Input 3

    10 13 15 20

    Sample Output 3

    30

    Hint

    1≤n,k,v,d≤106