$WorldOfOurOwn$World Of Our Own

⼩C在研究数组的xor。
她有⼀个长度为 $n$n 的数组 $A$A。
她每次会把 $a_{i-1}$ai−1​和 $a_i$ai​异或起来，然后 $A$A的长度会变成 $n-1$n−1
这么操作了 $n-1$n−1次之后得到了长度为 $1$1的数组。
她想知道在操作过程中每次的 $a_1$a1​为多少?
为了避免输出过⼤，请输出第 $j$j次操作后的 $a_1\times (j+1)$a1​×(j+1)的异或和( $0\le j\le n-1$0≤j≤n−1)。

$n\le 8\ast 10^6,a,b,c,d\le 10^9,a\&lt;d$n≤8∗106,a,b,c,d≤109,a<d

$正解部分$正解部分

将过程图画出如下 $\downarrow$↓
(请自行脑补将所有下标减 $1$1)

图中最左边一列的点从上向下分别表示第 $0,1,2,3$0,1,2,3 此操作后的 $a_1$a1​,
其左下角的数字表示其受数组中对应位置的异或和贡献,

发现贡献系数是符合杨辉三角的规律的, 用语言表达出来就是: $第i次操作后受位置j影响的贡献系数是C_i^j$第i次操作后受位置j影响的贡献系数是Cij​,
由于是异或操作, 当 贡献系数 是奇数的时候才会真正产生贡献 .

那么什么时候 贡献系数 为奇数呢 $?$?, 换句话说, 什么时候 $C_i^j$Cij​ 为奇数呢 $?$?
考虑在模 $2$2的意义下使用 $Lucas$Lucas 定理 : Cij​≡Ci%2j%2​∗Ci/2j/2​mod2,

先考虑第一项 $C_{i\%2}^{j\%2}$Ci%2j%2​, 当且仅当 $i\%2=0,j\%2=1$i%2=0,j%2=1 的时候 $C_{i\%2}^{j\%2}$Ci%2j%2​ 为 $0$0,
此时 $i$i 的二进制尾部为 $0$0, $j$j 的二进制尾部为 $1$1 , 由于是乘法, 这个 $0$0 会导致整个式子归零 .

再考虑第二项, 对 $C_{i/2}^{j/2}$Ci/2j/2​ 使用 $Lucas$Lucas 定理,
在二进制表示下相当于 $i$i 与 $j$j 同时去掉尾部的一个二进制位之后的一个递归过程, 回到 考虑第一项 的情况 .

于是综上所述可得: $当i\mathrm{\&amp;}j=j时,C_i^j=1,j位置的数对第i次操作的a_1有贡献.$当i&j=j时,Cij​=1,j位置的数对第i次操作的a1​有贡献.

$实现部分$实现部分

可以枚举 $j$j, 然后在 $j$j 的二进制上 “填” $1$1 得到一个可以贡献的 $i$i, 累计 $a_j$aj​的贡献 .

#include<bits/stdc++.h>
#define reg register
typedef long long ll;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 8500006;

int N;
int a;
int b;
int c;
int d;
int Rd[maxn];
int sum[maxn];

ll Ans;
ll A[maxn];

void Vio(){
        int cnt = 0;
        for(reg int i = N; i > 1; i --){
                Ans ^= A[1]*(++ cnt);
                for(reg int j = 1; j < i; j ++) A[j] = A[j]^A[j+1];
        }
        Ans ^= A[1]*(++ cnt);
        printf("%lld\n", Ans);
}

void Work(){
        for(reg int j = 0; j <= 22; j ++)
                for(reg int i = 0; i < N; i ++)
                        if(!(i & (1<<j))) A[i|(1<<j)] ^= A[i];
        for(reg int i = 0; i < N; i ++) Ans ^= A[i]*(i+1);
        printf("%lld\n", Ans);
}

int main(){
        scanf("%d%d%d%d%d", &N, &a, &b, &c, &d);
        A[0] = a;
        for(reg int i = 1; i < N; i ++) A[i] = (A[i-1]*A[i-1] + 1ll*b*A[i-1] + c) % d;
        Work();
        return 0;
}