小雨的三角形

小雨手上有一个填满了数字的三角形。这个三角形一共有 $n$ 层，其中第 $i$ 层共有 $i$ 个数，且第 $1$ 个数和第 $i$ 个数均为 $i$ 。其余的数中，第 $j$ 个数是上一层中第 $j-1$ 个数和第 $j$ 个数的和。小雨想知道这个三角形第 $x$ 层到第 $y$ 层所有数的和，一共有 $m$ 个询问。

Python(2.7.3) 解法, 执行用时: 24ms, 内存消耗: 3044K, 提交时间: 2019-07-20 16:01:38

n, m = map(int, raw_input().split())
rec = []
for i in range(m):
    x, y = map(int, raw_input().split())
    rec.append((x, y))

mod = (10**9+7)
def getAns(x, y):
    return (3*(2**x)*(2**(y-x)-1) + 2*(x-y))%mod

for i in range(m):
    print(getAns(rec[i][0]-1, rec[i][1]))

C++11(clang++ 3.9) 解法, 执行用时: 11ms, 内存消耗: 488K, 提交时间: 2020-02-26 10:49:53

#include<stdio.h>
const int p=1e9+7;
int a[3005];
int main()
{
	int n,m,b,c;
	a[1]=1;
	scanf("%d%d",&n,&m);
	for(int i=2;i<=n;i++)
	a[i]=(a[i-1]*2+2)%p;
	while(m--)
	{
		int ans=0;
		scanf("%d%d",&b,&c);
		for(int i=b;i<=c;i++)
		(ans+=a[i])%=p;
		printf("%d\n",ans);
	}
}

Python3(3.5.2) 解法, 执行用时: 53ms, 内存消耗: 4192K, 提交时间: 2019-07-12 21:12:56

n,m=map(int,input().split())
M=int(1e9+7)
for _ in range(m):
	x,y=map(int,input().split())
	print((3*(2**y-2**(x-1))+2*(x-y)-2)%M)

详情