fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define int long long
  5.  
  6. const int MOD = 1000000007;
  7. const int N = 3e5 + 5;
  8.  
  9. void add_mod (int &a, int b) {
  10.   if ((a += b) >= MOD) a -= MOD;
  11.   if (a < 0) a += MOD;
  12. }
  13.  
  14. int fact[N];
  15. int inv_fact[N];
  16.  
  17. int bin_pow (int a, int b) {
  18.   assert(b >= 0);
  19.   int ans = 1;
  20.   while (b > 0) {
  21.     if (b & 1)
  22.       ans = ans * a % MOD;
  23.     a = a * a % MOD;
  24.     b >>= 1;
  25.   }
  26.   return ans;
  27. }
  28.  
  29. void build_fact (int n) {
  30.   fact[0] = 1;
  31.   for (int i = 1; i <= n; i++) {
  32.     fact[i] = fact[i - 1] * i % MOD;
  33.   }
  34.   inv_fact[n] = bin_pow(fact[n], MOD - 2);
  35.   for (int i = n - 1; i >= 0; i--) {
  36.     inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
  37.   }
  38. }
  39.  
  40. int C (int k, int n) {
  41.   if (n < k)
  42.     return 0;
  43.   return (fact[n] * inv_fact[k]) % MOD * inv_fact[n - k] % MOD;
  44. }
  45.  
  46. int n, k;
  47.  
  48. void read_input() {
  49.   cin >> n >> k;
  50. }
  51.  
  52. int ans[N];
  53. int f[N], last_f[N];
  54.  
  55. void calc_dp() {
  56.   last_f[0] = 1;
  57.  
  58.   add_mod(ans[0], 1);
  59.  
  60.   for (int i = 1; i * i <= (2*k); i++) {
  61.     for (int s = i; s <= k; s++) {
  62.       add_mod(f[s], last_f[s - i]);
  63.       add_mod(f[s], f[s - i]);
  64.       if (s >= n + 1)
  65.         add_mod(f[s], -last_f[s - n - 1]);
  66.     }
  67.     for (int s = 0; s <= k; s++) {
  68.       if (i % 2 == 0)
  69.         add_mod(ans[s], f[s]);
  70.       else
  71.         add_mod(ans[s], -f[s]);
  72.       last_f[s] = f[s];
  73.       f[s] = 0;
  74.     }
  75.   }
  76. }
  77.  
  78. void solve() {
  79.   int res = 0;
  80.   for (int s = 0; s <= k; s++) {
  81.     add_mod(res, C(n - 1, n + k - s - 1) * ans[s] % MOD);
  82.   }
  83.   cout << res;
  84. }
  85.  
  86. int32_t main() {
  87.   ios_base::sync_with_stdio(0);
  88.   cin.tie(0);
  89.  
  90.   read_input();
  91.   build_fact(N-5);
  92.   calc_dp();
  93.   solve();
  94.  
  95.   return 0;
  96. }
  97.  
Success #stdin #stdout 0.01s 9044KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gA2mEj
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!