区间 Range

2019-11-11 05:59:41

字体：大中小

来源：转载

供稿：网友

由于%没有逆运算，直接树状数组或线段树会出问题 //考试时搞了半天树状数组，发现会出现0，只好暴力，居然有60分，正解真心不好想出来

正解思路：

把序列分成长度为k的若干块，每一块维护前缀和后缀乘积（代码中的f和g分别维护前缀后缀乘积）每个长度为k的区间对应了一整块或者前一块的后缀和后一块的前缀，直接乘起来就得到答案时间复杂度为O(N)

#include<cstdio>#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]; 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]; 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;}

上一篇：Maven使用阿里云源

下一篇：hdu 1176 免费馅饼