Description

 

Input

Output

 

Sample Input

sample1:4 2 105 1 1 10sample2:1000 97 9699835141 1668 505 2333

Sample Output

sample1:4sample2:1749769

 

Data Constraint

分析

这题赛场打的是部分分，逆元前缀乘积40points

然后比赛结束看题解发现自己最早的想法已经接近正解了（fk u）

一开始是想分块，维护区间乘积，然后空间和时间都不接受

其实只需要维护块内前缀乘积和后缀乘积即可，这样可以O(1)得到乘积并异或上去

#include 
      
       #include 
       
        using namespace std;const int N=10000001;int s[2*N];int sumq[2*N],sumn[2*N];int n,k,m,P,a,b,c,d;void Block(int x) {    int l=(x-1)*k+1,r=min(x*k,n);    sumq[l]=s[l];sumn[r]=s[r];    for (int i=l+1;i<=r;i++)    sumq[i]=1ll*sumq[i-1]*s[i]%P;    for (int i=r-1;i>=l;i--)    sumn[i]=1ll*sumn[i+1]*s[i]%P;}int main() {    freopen("range.in","r",stdin);    freopen("range.out","w",stdout);    scanf("%d%d%d",&n,&k,&P);    scanf("%d%d%d%d",&a,&b,&c,&d);    s[1]=a;    for (int i=2;i<=n;i++) s[i]=(1ll*s[i-1]*b+c)%d;    int m=n/k;    if (m*k