885.求组合数 I（模板）

佚名 4年前 (2020-02-05) 算法 1492人围观抢沙发百度已收录

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

O（n^2）数据范围 a*b =4e6

根据组合数公式：

代码：

import java.util.Scanner;

public class Main{
        static final int N=2005;
        static final int mod=(int)1e9+7;
        static int c[][]=new int[N][N];
        public static void main(String[] args) {
                Scanner scan=new Scanner(System.in);
                for(int i=0;i<N;i++)
                    for(int j=0;j<=i;j++)
                        if(j==0) c[i][j]=1;
                        else  c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
                int t=scan.nextInt();
                while(t-->0){
                        int a=scan.nextInt();
                        int b=scan.nextInt();
                        System.out.println(c[a][b]);
                }
        }
}