学校OJ上过了,洛谷0分
查看原帖
学校OJ上过了,洛谷0分
247162
zty1203楼主2022/8/4 20:44

其实在学校OJ上交的时候连样例都过不去,后来加的特判

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;
const ll p=1e9+7;
int T;
ll n,m;
ll jc[N],jc_inv[N],x,y,d[N];
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b)x=1,y=0;
	else{
		exgcd(b,a%b,y,x);
		y-=a/b*x;
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin>>T;jc[1]=1;
	for(int i=2;i<=N-10;i++){
		jc[i]=(jc[i-1]*i)%p;
	}
	exgcd(jc[N-10],p,x,y);
	jc_inv[N-10]=(x%p+p)%p;
	for(int i=N-11;i>=0;i--){
		jc_inv[i]=(jc_inv[i+1]*(i+1))%p;
	}
	for(int i=0;i<=N-10;i++){
		d[i]=(d[i-1]+((i&1)?-1:1)*jc_inv[i]+p)%p;
	}
	while(T--){
		cin>>n>>m;
		if (n - m == 1) cout<<0<<endl;
        else if (m == n) cout<<1<<endl;
        else 
		cout<<jc[n]%p*jc_inv[m]%p*jc_inv[n-m]%p*jc[n-m]%p*d[n-m]%p<<endl;
	}
}
2022/8/4 20:44
加载中...