Tính tổ hợp chập k của n

Submit solution
Points: 3
Time limit: 3.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Cho số nguyên dương \(n\) và cho số tự nhiên \(k\) nằm trong đoạn \([0,n]\) Hãy tính tổ hợp chập \(k\) của \(n\)

Input

Dòng đầu là số bộ test \(t (1 \le t \le 10) \)

Tiếp theo \(t\) dòng mỗi dòng chứa hai số \(k\) và \(n\) thỏa mãn \((0 \le k \le n \le 10^5)\)

Output

Kết quả tổ hợp chập \(k\) của \(n\) bởi vì kết quả quá lớn chỉ cần lấy phần dư của kết quả chia cho \(10^9+7\)

Ví dụ

Input

4
6 3
10 7
41 21
20 17

Output

20
120
128935337
1140
tichpx

Comments


  • 1
    LãoTam  commented on Nov. 2, 2021, 1:36 a.m.

    mn cho e hỏi e sai ở đâu với ạ

    #include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int a[100005],n,k,dp[10005][10005];
void tinh(){
    for(int i=0;i<10005;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i)dp[i][j]=1;
            else dp[i][j]=(dp[i-1][j-1]+dp[i-1][j])%mod;
            }
            }
            }
int main()
{   int t;cin>>t;
tinh();
while(t--){
    cin>>n>>k;
    cout<<dp[n][k]<<"\n";
}
}

    toàn bị segmentation fault


    • 1
      TICHPX  commented on Nov. 2, 2021, 8:45 a.m.

      Nó cho n tới 10^5 mà em chỉ khai báo dp có kích thước tới 10^4


      • 2
        LãoTam  commented on Nov. 2, 2021, 1:32 p.m.

        em cũng tăng lên 10^5 lại bị lỗi dịch ạ.


        • 1
          TICHPX  commented on Nov. 2, 2021, 2:10 p.m.

          Ồ lỗi dịch nhưng nộp vẫn được chỉ là bộ nhớ ở đây 98Mb nếu đủ thì ko sao không đủ thì MLE


          • 1
            LãoTam  commented on Nov. 2, 2021, 2:42 p.m.

            em đưa void tinh() đấy vào main thì lại bị TLE:((


            • 1
              TICHPX  commented on Nov. 3, 2021, 12:39 a.m. ← edited

              Bài toán này khó rồi, thuật toán của em chưa đủ mạnh


              • 1
                LãoTam  commented on Nov. 3, 2021, 1:44 a.m.

                dạ thầy. Em nghe nói bài này dùng quy hoạch động mới AC được:((


                • 1
                  TICHPX  commented on Nov. 4, 2021, 8:20 a.m.

                  thay vì dùng mảng 2 chiều em dùng mảng 1 chiều là được


  • 1
    TICHPX  commented on June 22, 2020, 6:50 a.m.

    Chắc phải làm thêm bài "lại là tổ hợp chập" nữa nhỉ