Transformation

The first line contains two positive integers $n$ and $k$ $(1 \leq n \leq 10^{18}, 1 \leq k \leq 10^5)$ , as described in the problem statement.

The next $k$ lines give two positive integers $a$ and $b$ $(1 \leq a \leq n, 1 \leq b \leq 100)$ respectively, indicating that there are $a$ numbers of $b$ in the array. This problem ensures that the sum of all $a$ values is equal to $n$ .

C++(g++ 7.5.0) 解法, 执行用时: 108ms, 内存消耗: 436K, 提交时间: 2023-05-29 16:12:39

#include<iostream>
using namespace std;
const long long mod=1e9+7;
int main(){
	long long n,m;
	cin>>n>>m;
	if(n==1){
		long long z,y;
		cin>>z>>y;
		cout<<y*y;
		return 0;
	}
	long long jishu=1;
	while(1){
		jishu*=2;
		if(jishu>=n) break;
	}
	end:;
	long long l=jishu/2;

	long long site=0;
	long long sum1=0;
	long long sum2=0;
	int flag=0;
	for(int i=0;i<m;i++){
		long long a,b;
		cin>>a>>b;
		if(flag==1){
			sum2+=(a*b)%mod;
			sum2%=mod;
			
			continue;
		}
		if(a+site<=l){
			sum1+=(a*b)%mod;
			sum1%=mod;
			site+=a;
		}
		else{
			
			sum1+=((((l-site))%mod)*b)%mod;
			sum1%=mod;
			sum2+=(((a-(l-site))%mod)*b)%mod;
			sum2%=mod;
			site=l;
			flag=1;
		}
	}
	cout<<(((sum1*sum1)%mod)+(sum2*sum2)%mod)%mod; 
}

Python3 解法, 执行用时: 569ms, 内存消耗: 4668K, 提交时间: 2023-05-26 21:41:47

import math
list1 = (input().split())
n = list1[0]
m = list1[1]
n = int(n)
m = int(m)
all = 0
mi = int(pow(2, math.floor(math.log2(n))))
len1 = 0
len2 = 0
if mi == n:
    len1 = n/2
    len2 = n/2
else:
    len1 = mi
    len2 = n - mi

i = 1
quanbu = 0
allnum = 0
while i <= m:
    list2 = (input().split())
    x = list2[0]
    y = list2[1]
    x = int(x)
    y = int(y)
    quanbu += x * y
    if x + allnum <= len1:
        all += x * y
        allnum += x
    else:
        all += (len1 - allnum) * y
        allnum = len1
    i += 1
all2 = quanbu - all
print( int((all * all + all2 * all2) % 1000000007))

C++(clang++ 11.0.1) 解法, 执行用时: 32ms, 内存消耗: 416K, 提交时间: 2023-07-05 14:21:53

#include<bits/stdc++.h>
using namespace std ;//好窒息 
typedef long long ll;
const ll mod=1e9+7;
ll n,k,d,a,b,ans,a1,a2,sum,pk=0;
int main(){
	scanf("%lld%lld",&n,&k);
	d=1;
	for(;d*2<n;)d=d*2;
//	cout << d ;
	for(int i=1;i<=k;i++){
		scanf("%lld%lld",&a,&b);
		if(d>=a)d-=a;
		else{
			if(!pk){
				a1=sum+(d%mod)*b;
	    		a1%=mod;
		    	pk++;
	   		}
		}
		sum=sum+(a%mod)*b;
		sum%=mod;
	}
	a2=sum+mod-a1;
	a2%=mod;
	ans=a1*a1%mod+a2*a2%mod;
	ans%=mod;
	cout<< ans ; 
}

详情