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


  • 0
    tungdao_123  commented on May 21, 2024, 6:56 p.m. ← edited

    code tham khao cac bạn phải học kiến thức về euclid mở rộng, nghịch đảo modun để áp dụng ct (a / b) % m = (a % m) * (b ^ -1 % m) % m.

    #include <bits/stdc++.h>
using namespace std;
#define ll long long
#define push_b push_back
#define ss stringstream
#define pqueue priority_queue
#define ft first
#define se second
int mod = 1e9 + 7;
ll Gcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    ll x1, y1;
    ll d = Gcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - y1 * (a / b);
    return d;
}

ll nghichdao(ll a, ll m, ll &x, ll &y){
    if(gcd(a, m) != 1) 
        return -1;
    else
        return Gcd(a, m, x, y);
}
ll dp[1000000];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T; cin >> T;
    dp[1] = dp[0] = 1;
    for(int i = 1; i <= 1e6; ++i){
        dp[i] = dp[i - 1] * i;
        dp[i] %= mod;
    } 
    while(T--){
        ll n, k; cin >> n >> k;
        ll gt1 = dp[n], gt2 =dp[k], gt3 = dp[n - k];
        ll gt_x = (gt2 * gt3) % mod;
        ll x, y;
        if(nghichdao(mod, gt_x, x, y) != -1){
            ll x1 = y;
            x1 = ((x1 % mod) + mod) % mod;
            cout << ((gt1 % mod) * (x1 % mod)) % mod << '\n';
        }
    }
}

  • 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ỉ