2021年创客大赛(C++)初中组 1.数列问题

给出以下定义：

一个首项为 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 取模的结果

输入样例#1： 

3
1 5 
2 5 
3 5

输出样例#1：

15
35
70

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

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

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

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

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

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

 附上AC代码 ( 虽然第一次提交的时候TLE了一个点，但还是有惊无险的卡过了 ) 

#include
#define ll long long
#define MOD 1000000007
#define MAXN 2000005//数据范围是1000000，但公式里有n+m，所以数组大小要*2
ll fac[MAXN+5];	
ll inv[MAXN+5];	
inline ll read()//快读
{
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c-48);c=getchar();}
	return x*f;
}
inline void write(ll x)//快写
{
    if(x<0){putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
ll mod(ll a,ll b)//快速幂
{
	ll ans=1;
	while(b)
	{
		if(b&1)
		ans=ans*a%MOD;
		a=a*a%MOD;
		b>>=1;
	}
	return ans;
}
void fain()//预处理处1~2000000的阶乘和逆元
{
	fac[0]=inv[0]=1;
	for (int i=1;i<=MAXN;i++)
	{
		fac[i]=fac[i-1]*i%MOD;
		inv[i]=mod(fac[i],MOD-2);	
	}
}
ll solve(ll n,ll m)//利用公式求结果
{
	return fac[n+m]*inv[n+1]%MOD*inv[m-1]%MOD;
}
int main()
{
	ll n,m,a,b;
	n=read();
	fain();//预处理
	for(int i=1;i<=n;i++)
	{
		a=read();b=read();
		write(solve((ll)a,(ll)b));
		putchar('n');
	}
	return 0;
}