1 条题解
-
1
拆前缀和是显然的。
我们只保留所有的前缀最小值,因为其他的不可能造成影响。
然后我们发现,即便是取模之后,答案的构成仍然是某些前缀。
因此我们维护每一次取模之后,若干个 表示还有 个 会在后续被处理。
这样子直接做应该就能拿很多分。
在这个过程中,有大量没有意义的计算。
比如形如 的前缀,他们对最终答案的贡献是比较确定的,但是我们仍然维护了它。
所以我们可以记 为前缀 进行一系列取模之后的和。
从后往前转移。记 为当前处理的前缀长度,每次二分一个 ,表示在这里会有不一样的贡献。
然后计算 会在这一步分裂出多少个完整的 ,由 转移到 ,并继续处理 。
由于每次有效的取模之后 不会超过 ,所以只会二分 次。对于询问,同样处理即可(也就是说这题还可以做到多组询问)。
总复杂度 。
#include<bits/stdc++.h> using namespace std; #define int long long #define lb(x) x&(-x) #define ls(p) (p<<1) #define rs(p) ((p<<1)|1) #define pii pair<int,int> #define F first #define S second #define mkp make_pair #define psb push_back #define vi vector<int> const int mod=1e9+7; const int N=2e5+1000,inf=1e15; int B; int n,L,R,a[N],f[N]; int b[N],btt; inline int qpow(int x,int y){ int sum=1; while(y){ if(y&1) sum=sum*x%mod; x=x*x%mod;y>>=1; }return sum; } inline int Sum(int x){ if(x<=0) return 0; x%=mod; return x*(x+1)%mod*B%mod; } int chk(int nw){ int ret=0; while(1){ if(a[n]>=nw){ ret=(ret+Sum(nw-1))%mod;break; }int l=1,r=n; while(l<r){ int mid=((l+r)>>1); if(a[mid]<nw) r=mid; else l=mid+1; } ret=(ret+(nw/a[l])%mod*f[l])%mod; nw=nw%a[l]; }return ret; } signed main(){ B=qpow(2,mod-2); ios::sync_with_stdio(0); cin.tie(0); freopen("modulo.in","r",stdin); freopen("modulo.out","w",stdout); cin>>n>>L>>R; for(int i=1;i<=n;i++){ int x;cin>>x; if(btt==0||x<b[btt]) b[++btt]=x; }n=btt; for(int i=1;i<=n;i++) a[i]=b[i]; f[n]=Sum(a[n]-1); for(int i=n-1;i>=1;i--){ int nw=a[i]; while(1){ if(a[n]>=nw){ f[i]=(f[i]+Sum(nw-1))%mod;break; }int l=i+1,r=n; while(l<r){ int mid=((l+r)>>1); if(a[mid]<nw) r=mid; else l=mid+1; } f[i]=(f[i]+(nw/a[l])%mod*f[l])%mod; nw=nw%a[l]; } } L=max(1ll,L); if(L>R){ cout<<0;return 0; } int ans=0; if(L!=1) ans=ans-chk(L); ans=ans+chk(R+1); ans=(ans%mod+mod)%mod; cout<<ans; return 0; }
- 1
信息
- ID
- 965
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 9
- 标签
- (无)
- 递交数
- 20
- 已通过
- 3
- 上传者