Minus K

输入第一行包含两个正整数n和q，之间使用一个空格符分隔，表示Cirno分裂冰块的次数，以及询问次数。
之后第二行包含n个正整数，相邻正整数之间使用一个空格符分隔，按照输入顺序的第i个正整数记作 $k_i$ ，表示会将冰块 $ICE_{i - 1}$ 分裂成 $k_i$ 块冰块 $ICE_i$ 。
之后连续输入q行，每行一个两个非负整数，之间使用一个空格符分隔，这种输入的第i行的两个整数记作 $l_i,\ r_i$ ，即题目描述中的每次询问。

数据规范：
* $1 \le n \le 99999$ .
* $1 \le q \le 99999$ .
* $1 \le k_i \le 99999$ .

C++14(g++5.4) 解法, 执行用时: 71ms, 内存消耗: 2792K, 提交时间: 2019-12-07 16:52:58

#include<cstdio>
#include<algorithm>
using namespace std;

#define ll long long
const int MOD=20090909;
const int Mn=1e5+17;
ll a[Mn],sum[Mn];

int main(){
	int n,q;scanf("%d%d",&n,&q);
	a[1]=1;
	for(int i=2;i<=n+1;++i) scanf("%lld",&a[i]);
	for(int i=2;i<=n+1;++i) a[i]=(a[i]*a[i-1])%MOD;
	for(int i=1;i<=n+1;++i) sum[i]=(sum[i-1]+a[i])%MOD;
	while(q--){
		int l,r;scanf("%d%d",&l,&r);
		printf("%lld\n",(sum[r+1]-sum[l]+MOD)%MOD);
	}
	return 0;
}

C(clang 3.9) 解法, 执行用时: 81ms, 内存消耗: 4428K, 提交时间: 2019-12-12 21:21:42

#include<stdio.h>
#define N 20090909
int main()
{
	int i,n,q,b,c,d;
	scanf("%d%d",&n,&q);
	long long a[100009];
	a[0]=1;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&b);
        a[i]=a[i-1]*b%N;
	}
	long long k[100009];
	k[0]=1;
	for(i=1;i<=n;i++)
	{
		k[i]=(k[i-1]+a[i])%N;	
	}
	for(i=1;i<=q;i++)
	{
		scanf("%d%d",&c,&d);
		if(c==0)printf("%d\n",k[d]);
		else printf("%lld\n",(k[d]-k[c-1]+N)%N);
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 88ms, 内存消耗: 2020K, 提交时间: 2020-02-16 15:47:17

#include<bits/stdc++.h>
using namespace std;
int mod=20090909;
long long s[100000],b;
int main()
{
	int n,q,a,l,r;
	scanf("%d%d",&n,&q);
	s[0]=1;b=1;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		b=b*a%mod;
		s[i]=(s[i-1]+b)%mod;
	}
	while(q--)
	{
		scanf("%d%d",&l,&r);
		if(l==0) b=0;
		else b=s[l-1];
		printf("%lld\n",(s[r]+mod-b)%mod);
	}
	return 0;
 }

详情