首页 > 学院 > 开发设计 > 正文

区间 Range

2019-11-11 05:10:35
字体:
来源:转载
供稿:网友

题目


由于%没有逆运算,直接树状数组或线段树会出问题 //考试时搞了半天树状数组,发现会出现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;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表