Howmanysequences?

NC214742. Howmanysequences?

描述

Sister bin has a whim. She wants to find a sequence of positive integers. All the numbers in the sequence are not greater than N, the length of the sequence is M, and all the numbers are not less than the numbers in front of it. Soon she found a sequence like this. But she thought it was not enough. She wanted to know how many such sequences were, but she was scared by the amazing data range. Now that she has found you, please help her solve this problem.

Because the result may be very large, please output the value after taking the modulus of 1e9 + 7.

输入描述

The first line contains one integer T（T ≤ 1,000）, the number of test cases.
For each test case, there are two integers in one line in the following format:
N M
(1≤ N, M ≤ 10⁶ )

输出描述

For each group of test data, the output line contains an integer representing the number of sequences that meet the conditions after taking the modulus of 1e9 + 7.

示例1

输入:

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 248ms, 内存消耗: 31600K, 提交时间: 2021-07-04 16:47:53

#include<iostream>
#define int long long
using namespace std;
const int N=2000010,mod=1e9+7;
int frac[N],inv[N];
int n,m;
int qsm(int x,int y){
	int res=1;
	while(y){
		if(y&1){
			res=res*x%mod;
		}
		x=x*x%mod;
		y>>=1;
	}
	return res;
}
signed main(){
	
	int t;cin>>t;
	
	frac[0]=1,inv[0]=1;
	
	for(int i=1;i<N;i++){
		frac[i]=frac[i-1]*i%mod;
		inv[i]=qsm(frac[i],mod-2);
	}
	
	while(t--){
		int n,m;cin>>n>>m;
		cout<<frac[m+n-1]*inv[m]%mod*inv[n-1]%mod<<endl;
	}
	return 0;
}

上一题

下一题

详情

Because the result may be very large, please output the value after taking the modulus of 1e9 + 7.