باکتری درختی کامل

 avatar
unknown
c_cpp
a year ago
1.5 kB
3
Indexable
//Alir3za.Zar3 -> Shiraz , Iran
#include <bits/stdc++.h>
using namespace std;
void debug(int out){ cerr << out << endl; }

#define int unsigned long long
#define loop(i , l , r) for (int i = l; i <= r; i++)
#define arc(i , r , l) for (int i = r; i >= l; i--)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define Turbo ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sep " "
//#define endl "\n"

const int Delta = 10729 , D = 1e9+7;
int pw (int base , int e , int M)
{ return e? pw(base*base%M,e>>1,M)*(e&1 ? base:1)%M:1; }

const int mxxn = 5e3+10;
int N , T , K , nCr_leaf[mxxn] , nCr_all[mxxn];
void fill_nCr()
{
    int F_leaf[mxxn] , F_all[mxxn] , Inv[mxxn];
    F_leaf[0] = F_all[0] = 1; Inv[0] = 1;
    loop(i,1,mxxn-1){
        F_leaf[i] = (F_leaf[i-1]*((N-i+1)%D))%D;
        F_all[i] = (F_all[i-1]*((N-i-T+1)%D))%D;
        Inv[i] = (Inv[i-1]*i)%D;
    } Inv[mxxn-1] = pw(Inv[mxxn-1] , D-2 , D);
    arc(i,mxxn-1,1){ Inv[i-1] = (Inv[i]*i)%D; }

    loop(i,1,mxxn-1){
        nCr_leaf[i] = (Inv[i]*F_leaf[i])%D;
        nCr_all[i] = (Inv[i]*F_all[i])%D;
    }
}

void Engine ()
{
    int n; cin >> n >> T >> K;
    N = 1; loop(i,1,n){ N*=2; }
    fill_nCr();
    int leaf = nCr_leaf[T];
    int others = nCr_all[K-T+1];
    int out = (leaf*others %D)%Delta;
    cout << out << endl;
}

signed main()
{
    Turbo
    int Tc = 1; //cin >> Tc;
    while (Tc--){ Engine(); }
}
Editor is loading...
Leave a Comment