Advertisement
Guest User

Untitled

a guest
Jul 19th, 2019
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <stdio.h>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. using solt = unsigned long long;
  9. solt mod = 1000000000 + 7;
  10. solt power(solt a, solt n){
  11.     if (n == 1)
  12.         return a % mod;
  13.     if (n % 2 == 0){
  14.         solt b = power(a, n / 2);
  15.         return (b * b) % mod;
  16.     }
  17.     else{
  18.         solt b = power(a, n - 1);
  19.         return (a * b) % mod;
  20.     }
  21. }
  22. solt cnk (solt n, solt k, vector<solt> &fac){
  23.     if (k > n)
  24.         return 0;
  25.     if (k == n)
  26.         return 1;
  27.     solt under = (fac[n - k] * fac[k]) % mod;
  28.     under = power(under, mod - 2) % mod;
  29.     solt asw = (fac[n] * under) % mod;
  30.     return asw;
  31. }
  32. int main(){
  33.     solt n = 0, m = 0, l = 0;
  34.     scanf("%llu %llu %llu", &n, &m, &l);
  35.  
  36.     vector <solt> fac (n + 1);
  37.     fac[0] = 1;
  38.     for (solt i = 1; i < n + 1; i++){
  39.         fac[i] = (fac[i - 1] * i) % mod;
  40.     }
  41.     solt asw = 0;
  42.     for(solt k = 1; k <= l; k++){
  43.         if(n < m * k)
  44.             continue;
  45.         asw+=cnk(n, m * k, fac);
  46.         asw %= mod;
  47.     }
  48.     printf("%llu\n", asw);
  49.     return 0;
  50.  
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement