fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. // #define int long long
  7. using ll = long long;
  8. const int N = 1e5 + 5;
  9. const int MOD = 1e9 + 7;
  10. int n, k;
  11. int POW(ll a, int p) {
  12.     ll ans = 1;
  13.     for (; p > 0; p >>= 1, a = a * a % MOD) if (p & 1) ans = ans * a % MOD;
  14.     return ans;
  15. }
  16.  
  17. ll fact[N * 2], invf[N * 2];
  18. void init(int n) {
  19.     fact[0] = 1;
  20.     for (int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
  21.     invf[n] = POW(fact[n], MOD - 2);
  22.     for (int i = n - 1; i >= 0; i--) invf[i] = invf[i + 1] * (i + 1) % MOD;
  23. }
  24. inline int nCr(int n, int k) {
  25.     if (k < 0 || n < k) return 0;
  26.     return fact[n] * invf[k] % MOD * invf[n - k] % MOD;
  27. }
  28.  
  29. const int SQ = 448;
  30. int dp[SQ][N];
  31. int csG[N];
  32. void add(int &u, int v) {
  33.     u += v;
  34.     if (u >= MOD) u -= MOD;
  35. }
  36. void sub(int &u, int v) {
  37.     u -= v;
  38.     if (u < 0) u += MOD;
  39. }
  40. void calcDp(int n, int k) {
  41.     int lim = sqrt(k);
  42.     while(lim * (lim + 1) / 2 < k) lim++;
  43.     lim = min(lim, n);
  44.     dp[0][0] = 1;
  45.     csG[0] = 1;
  46.     for (int i = 1; i <= lim; i++) {
  47.         for (int j = i; j <= k; j++) {
  48.             add(dp[i][j], dp[i - 1][j - i]);
  49.             add(dp[i][j], dp[i][j - i]);
  50.             if (j - (n + 1) >= 0) sub(dp[i][j], dp[i - 1][j - (n + 1)]);
  51.             if (i & 1) sub(csG[j], dp[i][j]);
  52.             else add(csG[j], dp[i][j]);
  53.         }
  54.     }
  55. }
  56.  
  57.  
  58. signed main() {
  59.     cin.tie(NULL)->sync_with_stdio(false);
  60.     if(ifstream("Input.inp")) {
  61.         freopen("Input.inp", "r", stdin);
  62.         freopen("Output.out", "w", stdout);
  63.     }
  64.     cin >> n >> k;
  65.     init(n + k);
  66.     calcDp(n, k);
  67.     int ans = 0;
  68.  
  69.     for (int i = 0; i <= k; i++) {
  70.         add(ans, 1LL * csG[i] * nCr(n + k - i - 1, n - 1) % MOD);
  71.         // cerr << nCr(n + k - i - 1, n - 1) << " ";/
  72.     }
  73.     cout << ans;
  74.     return 0;
  75. }
  76.  
  77.  
Success #stdin #stdout 0.01s 9616KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/qaRuGx
language:
C++14 (gcc 8.3)
created:
6 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!