数列问题

站外题

题目描述

给出以下定义： 一个首项为 1，每一项之间差为 1 的一阶等差数列为 W_1 阶等差数列（例如：1,2,3…是 W_1阶等差数列）

一个首项为 1，每一项之间差为 W_1 阶等差数列的数列为 W_2 阶等差数列（例如：1,3,6…是 W_2 阶等差数列）

一个首项为 1，每一项之间差为 W_2 阶等差数列的数列为 W_3 阶等差数列（例如：1,4,10…是 W_3 阶等差数列）

……以此类推

现在，给出 n,m，请你快速求出 W_n 阶等差数列前 m 项的和对 1e9+7 取模后的结果

输入输出

输入格式：

共 T 组数据

第一行输入一个正整数 T，表示数据组数。

接下来 T 行，每行输入 2 个正整数 n, m。

输出格式：

输出共 T 行，每行输出一个正整数，

W_n 阶等差数列前 m 项之和对 1e9+7 取模的结果

样例

输入样例

3

1 5

2 5

3 5

输出样例：

15

35

70

补充说明

【数据范围】

对于 20%的数据，保证 0≤T, n, m≤10；

对于另外 15%的数据，保证 n=1；

对于另外 25%的数据，保证 n=2；

对于另外 20%的数据，保证 T=1；

对于 100%的数据，保证有 0≤n, m≤1e6，0≤T≤1e6

时间限制：1s 空间限制：128M

错误代码

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
long long calc(int n,int m){
	long long sum=0;
	long long cur=1;
	for(int i=1;i<=m;i++){
		sum=(sum+cur)%mod;
		long long diff=0;
		for(int j=1;j<i;j++){
			long long idiff=j;
			for(int k=2;k<=n;k++){
				long long temp=idiff;
				idiff=0;
				for(int l=1;l<=j;l++){
					idiff=(idiff+temp)%mod;
				}
			}
			diff=(diff+idiff)%mod;
		}
		cur=(cur+diff)%mod;
	}
	return sum;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		cout<<calc(n,m)<<endl;
	}
	return 0;
}

求调，在线等急