fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. const int maxN = 3e6 + 5;
  6. const int MOD = 1e9 + 7;
  7. int n, k, L, H;
  8.  
  9. int fact[maxN], inv[maxN];
  10.  
  11. int Pow(int a, int b) {
  12.     if (b == 0) return 1;
  13.     int res = Pow(a, b / 2); res = 1ll * res * res % MOD;
  14.     if (b & 1) res = 1ll * res * a % MOD;
  15.     return res;
  16. }
  17.  
  18. int C(int k, int n) {
  19.     if(k>n) return 0;
  20.     if(k<0 or n<0) return 0;
  21.     return (1ll * fact[n] * inv[n - k] % MOD) * inv[k] % MOD;
  22. }
  23.  
  24. signed main() {
  25.     cin >> n >> k>>L>>H;
  26.  
  27.     fact[0] = 1;
  28.     for (int i = 1; i <= n+k; i++) {
  29.         fact[i] = 1ll * fact[i - 1] * i % MOD;
  30.     }
  31.  
  32.     inv[n+k] = Pow(fact[n+k], MOD - 2);
  33.     for (int i = n+k - 1; i >= 0; i--) {
  34.         inv[i] = 1ll * (i + 1) * inv[i + 1] % MOD;
  35.     }
  36.     n-=k*L;
  37.     H=H-L;
  38.  
  39.     int res= C(k-1, n+k-1);
  40.  
  41.     for(int i=1;i<=k;i++){
  42.       int x = C(k-1, n+k-1-i*(H+1));
  43.       if(i%2!=0){
  44.         res = (res - x*C(i,k)%MOD + MOD) % MOD;
  45.       }
  46.       else{
  47.         res = (res + x*C(i,k)%MOD) % MOD;
  48.       }
  49.     }
  50.     cout<<res;
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 5592KB
comments (?)
stdin 
6 3 0 6
stdout 
28
https://ideone.com/fV55aS
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!