java_day3

目标: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包读取数据

上一篇:Linux基础-day3


下一篇:Java基础学习day3---数组