باکتری درختی کامل
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