fork download
copy 
  1. // #pragma GCC optimize("O3", "unroll-loops")
  2. // #pragma GCC target("avx2", "bmi", "bmi2", "lzcnt", "popcnt")
  3.  
  4. #include <bits/stdc++.h>
  5. #define ldb long double
  6. //#define double ldb
  7. #define db double
  8. #define unomap unordered_map
  9. #define unoset unordered_set
  10. #define endl '\n'
  11. #define str string
  12. #define strstr stringstream
  13. #define sz(a) (int)a.size()
  14. #define ll long long
  15. // #define int ll
  16. #define pii pair <int, int>
  17. #define pll pair <ll, ll>
  18. #define Unique(a) a.resize(unique(all(a)) - a.begin())
  19. #define ull unsigned ll
  20. #define fir first
  21. #define sec second
  22. #define idc cin.ignore()
  23. #define lb lower_bound
  24. #define ub upper_bound
  25. #define all(s) s.begin(), s.end()
  26. #define rall(s) s.rbegin(), s.rend()
  27. #define rev reverse
  28. #define gcd __gcd
  29. #define pushb push_back
  30. #define popb pop_back
  31. #define pushf push_front
  32. #define popf pop_front
  33. #define mul2x(a, x) a << x
  34. #define div2x(a, x) a >> x
  35. #define lcm(a, b) (a / __gcd(a, b) * b)
  36. #define log_base(x, base) log(x) / log(base)
  37. #define debug cerr<<"No errors!",exit(0);
  38. #define forw(i, a, b)  for (int i = a; i <= b; ++i)
  39. #define forw2(i, a, b) for (ll i = a; i <= b; ++i)
  40. #define fors(i, a, b)  for (int i = a; i >= b; --i)
  41. #define fors2(i, a, b) for (ll i = a; i >= b; --i)
  42. #define pqueue priority_queue
  43. #define sqrt sqrtl
  44. #define i128 __int128
  45. #define popcount __builtin_popcountll
  46. #define BIT(x, i) (((x) >> (i)) & 1)
  47. #define MASK(x) ((1LL) << (x))
  48. #define want_digit(x) cout << fixed << setprecision(x);
  49. #define excuting_time 1000.0 * clock() / CLOCKS_PER_SEC
  50. #define mapa make_pair
  51. using namespace std;
  52. const int MOD = 1e9 + 7; // 998244353;
  53. const int inf = 1e9;
  54. const ll INF = 1e18; // MASK(63) - 1
  55. const int N = 2e7;
  56.  
  57. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  58. ll random(const ll &L, const ll &R) {
  59.     return uniform_int_distribution<ll> (L, R) (rng);
  60. }
  61.  
  62.  
  63. /* -------~~~~~~===== END OF TEMPLATE =====~~~~~~------- */
  64.  
  65.  
  66. int fac[N + 5], inv[N + 5];
  67.  
  68. ll power(ll a, ll b) {
  69.     ll res = 1;
  70.     while (b) {
  71.         if (b & 1) res = res * 1LL * a % MOD;
  72.         a = a * 1LL * a % MOD;
  73.         b >>= 1;
  74.     }
  75.     return res;
  76. }
  77.  
  78. ll C(ll n, ll k) {
  79.     if (n < 0 || k < 0 || k > n) return 0;
  80.     return fac[n] * 1LL * inv[k] % MOD * 1LL * inv[n - k] % MOD;
  81. }
  82.  
  83. void solve() {
  84.     ll S, n, L, H;
  85.     cin >> S >> n >> L >> H;
  86.  
  87.     fac[0] = 1;
  88.     forw2 (i, 1, N) fac[i] = fac[i - 1] * 1LL * i % MOD;
  89.     inv[N] = power(fac[N], MOD - 2);
  90.     fors2 (i, N, 1) inv[i - 1] = inv[i] * 1LL * i % MOD;
  91.  
  92.     if (S < n * 1LL * L) { cout << "0\n"; return; }
  93.     ll S2 = S - n * 1LL * L, D = H - L + 1, ans = 0;
  94.     forw2 (k, 0, n) {
  95.         ll curr = C(n, k) * 1LL * C(S2 - k * 1LL * D + n - 1, n - 1) % MOD;
  96.         if (k & 1) ans = (ans - curr + MOD) % MOD;
  97.         else ans = (ans + curr) % MOD;
  98.     }
  99.     cout << ans << endl;
  100. }
  101.  
  102. signed main() {
  103.     ios::sync_with_stdio(false), cin.tie(nullptr);
  104.     srand(time(NULL));
  105.     #define name "test"
  106.     /*
  107.     if (fopen(name".INP", "r")) {
  108.         freopen(name".INP", "r", stdin);
  109.         freopen(name".OUT", "w", stdout);
  110.     }
  111.     */
  112.     bool testCase = false;
  113.     int numTest = 1;
  114.     // cin >> numTest;
  115.     forw (i, 1, numTest) {
  116.         if (testCase) cout << "Case #" << i << ": ";
  117.         solve();
  118.     }
  119.     return 0;
  120. }
  121.  
  122. /*
  123.   /\__/\
  124.  (=^.^= )
  125.  (") (")_/
  126. */
Success #stdin #stdout 0.25s 159988KB
comments (?)
stdin
copy 
6 2 2 6
stdout
copy 
3
https://ideone.com/qvsxhc
language:
C++14 (gcc 8.3)
created:
13 days 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!