Generation I

The input starts with one line containing exactly one integer T which is the number of test cases. (1 ≤ T ≤ 20)

Each test case contains one line with two integers N and M indicating the number of sets and the range of integers. (1 ≤ N ≤ 10¹⁸, 1 ≤ M ≤ 10¹⁸, $1 \le \min\{N,M\} \le10^{6}$ )

C++14(g++5.4) 解法, 执行用时: 358ms, 内存消耗: 4288K, 提交时间: 2018-08-04 12:50:51

#include<bits/stdc++.h>
using namespace std;
#define N 1000010
#define mo 998244353
int Inv[N];
int main(){
	int i;
	Inv[1]=1;
	for (i=2;i<N;i++){
		Inv[i]=1LL*(mo-mo/i)*Inv[mo%i]%mo;
	}
	int Case,Tt;
	scanf("%d",&Case);
	for (Tt=1;Tt<=Case;Tt++){
		long long n,m;
		scanf("%lld%lld",&n,&m);
		int Ans=0,Sum=1;
		for (i=1;i<=min(n,m);i++){
			Sum=1LL*Sum*((m-i+1)%mo)%mo;
			if (i>1){
				Sum=1LL*Sum*((n-i+1)%mo)%mo*Inv[i-1]%mo;
			}
			Ans=(Ans+Sum)%mo;
		}
		printf("Case #%d: %d\n",Tt,Ans);
	}	
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 220ms, 内存消耗: 8288K, 提交时间: 2018-08-04 12:57:12

#include<bits/stdc++.h>
using namespace std;
#define maxn 1001000
#define ll long long
const int p=998244353;
ll n,m;
ll inv[maxn];
int main()
{
	int T;
	scanf("%d",&T);
	inv[1]=inv[0]=1;
	for(int i=2;i<maxn;++i) inv[i]=(p-p/i)*inv[p%i]%p;
	for(int cas=1;cas<=T;++cas)
	{
		scanf("%lld%lld",&n,&m);
		ll fi=m%p,se=1;
		ll ans=0;
		for(int i=1;i<=n&&i<=m;++i)
		{
			ans=(ans+fi*se)%p;
			fi=fi*((m-i)%p)%p;
			se=se*((n-i)%p)%p*inv[i]%p;
		}
		printf("Case #%d: %lld\n",cas,ans);
	}
	return 0;
}

详情