标签：数论，前缀和，位运算
小C在研究数组的xor。
她有一个长度为n的数组A。
她每次会把ai−1和ai异或起来，然后A的长度会变成n−1
这么操作了n−1次之后得到了长度为1的数组。
她想知道在操作过程中每次的a1为多少?
为了避免输出过大，请输出第j次操作后的a1×(j+1)的异或和(0≤j≤n−1)。
输入格式
一行五个整数n,a,b,c,d
数组A以如下方式生成，
输出格式
一行一个整数表示答案。
样例一
input
5 3 2 4 15
output
89
样例解释
3 4 13 4 13
7 9 9 9
14 0 0
14 0
14
3 xor (7∗2) xor (14∗3) xor (14∗4) xor (14∗5)=89
限制于约定
分析：
30分 直接暴力模拟
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
unsigned long long n,a,b,c,d,ans;
unsigned long long x[maxn],y[maxn];
int main()
{
// scanf("%I64d%I64d%I64d%I64d%I64d",&n,&a,&b,&c,&d);
cin>>n>>a>>b>>c>>d;
x[1]=a;
for(int i=2;i<=n;i++)x[i]=((x[i-1]*x[i-1])+b*x[i-1]+c)%d;
for(int i=1;i<=n;i++)
{
ans=ans^(x[1]*i);
for(int j=1;j<=n-i+1;j++)
y[j]=x[j]^x[j+1];
memset(x,0,sizeof(0));
for(int j=1;j<=n-i;j++)x[j]=y[j];
}
cout<<ans<<endl;
return 0;
}
50分 经过输出每一次循环的x[]数组，不难发现，当a[2]==0时，a[1]不再发生变化，可以跳出循环，break，单独计算后面每个a[1]的异或和
Code
#include<bits/stdc++.h>
using namespace std;
const int maxn=8000005;
unsigned long long n,a,b,c,d,ans;
unsigned long long x[maxn],y[maxn];
int main()
{
cin>>n>>a>>b>>c>>d;
x[1]=a;
for(int i=2;i<=n;i++)x[i]=((x[i-1]*x[i-1])+b*x[i-1]+c)%d;
int i;
for(i=1;i<=n;i++)
{
ans=ans^(x[1]*i);
for(int j=1;j<=n-i+1;j++)
y[j]=x[j]^x[j+1];
memset(x,0,sizeof(0));
for(int j=1;j<=n-i;j++)x[j]=y[j];
if(x[2]==0)break;
}
for(int k=i+1;k<=n;k++)ans=ans^(x[1]*k);
cout<<ans<<endl;
return 0;
}
100分 这题的求解过程可以看成每次在A当前位置上方和右上方的数的异或，并且每次长度减1，等价于有多少种方案走到这个位置，假设A当前位置为i+1一个点为第j个数列的第一项，那么从i到j会向下走j步，向左走i步，方案数为C(I,j)，
那么第j个数列的第1项就是C(0,j)个a[1],C(1,j)个a[2],C(I,j)个a[i+1]~C(j,j)个a[j+1]的异或
如果i到j有奇数个方案，那么i到j就有贡献，否则没有，考虑C（I,j）的奇偶性
根据lucas定理，
C（I mod 2,j mod 2）=0当且仅当j mod 2=0而I mod 2=1，那么C（I,j）为奇数当且仅当每个二进制位都没有这种情况，即I and j=i
对于每个j的答案，记为b[j]，它等于所有满足I and j=i的a[i]的异或和
注意到这里的子集可以看做高维的前缀和，可以看成数组a有m堆，每一堆都是0或1，表示下标的一个二进制位，我们要对a一个m维的前缀和得到b，b[j]就是把j中一些1的位变成0得到i的a[i]的和
时间复杂度为O（n log n），那么大的数据范围，这也能水过？？？23333超神的评测机
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=(1<<23)+7;
int n,a,b,c,d;
LL x[maxn];
int main()
{
cin>>n>>a>>b>>c>>d;
x[0]=a;
for(int i=1;i<n;i++)x[i]=(1LL*x[i-1]*x[i-1]+1LL*b*x[i-1]+c)%d;
for(int j=0;j<23;j++)
for(int i=0;i<n;i++)
if(!(i>>j&1))x[i|(1<<j)]^=x[i];
LL ans=0;
for(int i=0;i<n;i++)ans^=1LL*(i+1)*x[i];
cout<<ans<<endl;
return 0;
}
本文可以转载，但必须附上原文链接，否则你会终生找不到妹子！！！欢迎关注我的CSDN: ahyjjr
