World of our own(noip2017模拟题)

Posted by yjjr's blog on February 6, 2018

标签:数论,前缀和,位运算


C在研究数组的xor

她有一个长度为n的数组A

她每次会把ai−1ai异或起来,然后A的长度会变成n−1

这么操作了n−1次之后得到了长度为1的数组。

她想知道在操作过程中每次的a1为多少?

为了避免输出过大,请输出第j次操作后的a1×(j+1)的异或和(0j≤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 (72) xor (143) xor (144) xor (145)=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