noip2016练习题（2.区间）

#include<cstdio>//2016noip练习题，2，区间；
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn=20000005;
int n,k,P,A,B,C,D;
int s[maxn],f[maxn],g[maxn];
int ans;

int main()
{
 freopen("range.in","r",stdin);
 freopen("range.out","w",stdout);
 scanf("%d%d%d%d%d%d%d",&n,&k,&P,&A,&B,&C,&D);
 s[1]=A;
 for(int i=2;i<=n;i++)
  s[i]=((LL)s[i-1]*B+C)%D;
 for(int i=1;i<=n;i++)
  if((i-1)%k==0)
   f[i]=s[i];   //f数组记录区间前缀和
  else
   f[i]=(LL)f[i-1]*s[i]%P;//当不是整区间时，记录前部分乘积；
 g[n+1]=1;
 for(int i=n;i;i--)
  if(i%k==0)
   g[i]=s[i];//g数组记录后缀和
  else
   g[i]=(LL)g[i+1]*s[i]%P;
 for(int i=1;i+k-1<=n;i++)
  if((i-1)%k==0)
   ans^=g[i];//当恰好为区间时，乘积即为后缀和
  else
   ans^=(LL)f[i+k-1]*g[i]%P;//当不为整区间使，乘积为前缀积×后缀积
 printf("%d\n",ans);
 return 0;
}