目标:Java web开发
给定一万组左右询问,每组询问给定两个整数 a和b,1≤b≤a≤\(10^5\)。
请你在1秒内算出,\(C_{a}^{b}\)(结果可能太大,对\(10^9\)+7取模即可)的值。
输入样例(4组询问时):
4
6 3
100000 999
1314 521
12345 6789
输出样例:
20
625779904
175198685
202367423
import java.util.*;//常用的packge还有io,net,sql;创建packge相当于创建文件夹,包名需小写
public class Main{//
//java类的初始化顺序————静态变量>静态初始化块>main函数>变量>初始化块>构造函数
static final int mod=1000000007, N=100010;//final,常量关键字
static long[] fact=new long[N];//java不支持高位截断,不能讲long型数据转换为int型数据
static long[] infact=new long[N];//N要是int型,因为数组长度要是int型
/*数太大就要讨论变量存储空间
char类型2个字节,因为用的Uni-code编码(也就是是将世界上所有的文字用2个字节统一进行编码)
int,float类型4个字节
long,double类型8个字节
*/
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
fact[0]=infact[0]=1;
for(int i=1;i<N;i++){
fact[i]=fact[i-1]*i%mod;
infact[i]=qpow(fact[i],mod-2);//快速幂
}
int n=sc.nextInt();
for(int i=0;i<n;i++){
int a=sc.nextInt(),b=sc.nextInt();
System.out.println((long)fact[a]*infact[a-b]%mod*infact[b]%mod);//逆元
}
/*这道题不会逆元就放弃吧,几十位的数,表示都很难表示,更别说再除以一个数了。
Python党可能表示不服,但Python算这一个问题,10分钟远远不够。
*/
}
public static long qpow(long x,int y){
long res=1;
while(y>0){//判断成立的条件永远要是boolean类型,其他类型(比如整型)是不行滴。
if((y&1)==1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
}/*吐槽:java约束条件太多了,没有c++写起来方便,继承都只能是单继承,也太小心翼翼了吧。
呜呜呜,隐式类型转换,你在哪里?
*/
明天可能开io包读取数据