Paste Search Dynamic
Recent pastes
ans
  1. #include <stdio.h>
  2. #define N 200000
  3. #define mod 1000000007
  4. int add(int a, int b) {
  5.     return a + b >= mod ? a + b - mod : a + b;
  6. }
  7. int sub(int a, int b) {
  8.     return a >= b ? a - b : a - b + mod;
  9. }
  10. int mul(int a, int b) {
  11.     return 1ll * a * b % mod;
  12. }
  13. int fac[N + 5], ifac[N + 5], inv[N + 5];
  14. void prework(int n) {
  15.     fac[0] = fac[1] = inv[0] = inv[1] = ifac[0] = ifac[1] = 1;
  16.  
  17.     for (int i = 2; i <= n; i++)
  18.         fac[i] = mul(fac[i - 1], i);
  19.  
  20.     for (int i = 2; i <= n; i++)
  21.         inv[i] = mul(sub(mod, mod / i), inv[mod % i]);
  22.  
  23.     for (int i = 2; i <= n; i++)
  24.         ifac[i] = mul(ifac[i - 1], inv[i]);
  25. }
  26. int C(int n, int m) {
  27.     return mul(fac[n], mul(ifac[m], ifac[n - m]));
  28. }
  29. int n, k, f[N + 5], ans;
  30. int main() {
  31.     scanf("%d%d", &n, &k);
  32.     prework(n + k);
  33.  
  34.     for (int i = 0; i <= k; i++)
  35.         f[i] = C(n + i - 1, i);
  36.  
  37.     for (int i = 0; i <= n; i++) {
  38.         int t = i * (i + 1) / 2;
  39.  
  40.         if (t > k)
  41.             break;
  42.  
  43.         if (i) {
  44.             for (int j = i; j <= k - t; j++)
  45.                 f[j] = add(f[j], f[j - i]);
  46.  
  47.             for (int j = k - t; j >= n - i + 1; j--)
  48.                 f[j] = sub(f[j], f[j - (n - i + 1)]);
  49.         }
  50.  
  51.         if (i & 1)
  52.             ans = sub(ans, f[k - t]);
  53.         else
  54.             ans = add(ans, f[k - t]);
  55.     }
  56.  
  57.     printf("%d", ans);
  58.     return 0;
  59. }
Parsed in 0.009 seconds