1 条题解

  • 1
    @ 2026-11-3 12:03:36

    拆前缀和是显然的。

    我们只保留所有的前缀最小值,因为其他的不可能造成影响。

    然后我们发现,即便是取模之后,答案的构成仍然是某些前缀。

    因此我们维护每一次取模之后,若干个 (pi,qi)(p_i,q_i) 表示还有 qiq_i 个 pip_i 会在后续被处理。

    这样子直接做应该就能拿很多分。

    在这个过程中,有大量没有意义的计算。

    比如形如 [0,ax)[0,a_x) 的前缀,他们对最终答案的贡献是比较确定的,但是我们仍然维护了它。

    所以我们可以记 fif_i 为前缀 [0,ai)[0,a_i) 进行一系列取模之后的和。

    从后往前转移。记 ww 为当前处理的前缀长度,每次二分一个 ax<wa_x < w ,表示在这里会有不一样的贡献。

    然后计算 ww 会在这一步分裂出多少个完整的 axa_x,由 fxf_x 转移到 fif_i,并继续处理 w mod xw\:mod\: x。

    由于每次有效的取模之后 ww 不会超过 w2\frac{w}{2},所以只会二分 O(log⁡V)O(\log V) 次。对于询问,同样处理即可(也就是说这题还可以做到多组询问)。

    总复杂度 O(nlog⁡nlog⁡V)O(n\log n\log V)。

    #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

    [2026济南登峰营] D1 P4 模刀削面(modulo) - 文件读写

    信息

    ID
    965
    时间
    1000ms
    内存
    512MiB
    难度
    9
    标签
    (无)
    递交数
    20
    已通过
    3
    上传者