fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define print(x) cout << "[" << (x) << "]"
  4. const int N = 1e5 + 5;
  5. const int B = 605;
  6. using ll = long long;
  7. const ll mod = 1e9 + 7;
  8. ll fac[2*N], inv[2*N];
  9. ll Exp(ll a, ll b) {
  10.     if (!b) return 1LL;
  11.     ll tmp = Exp(a, b / 2);
  12.     tmp = tmp * tmp % mod;
  13.     if (b & 1) tmp = tmp * a % mod;
  14.     return tmp;
  15. }
  16.  
  17. ll Euler(int m, int n) {
  18.     return fac[n + m - 1] * inv[n - 1] % mod * inv[m] % mod;
  19. }
  20.  
  21. void add(ll &x, ll y) {
  22.     x += y;
  23.     if (x >= mod) x -= mod;
  24. }
  25.  
  26. int n, k;
  27. ll dp[B][N], f[2][N];
  28. int main() {
  29.     fac[0] = 1;
  30.     for (int i = 1; i <= 2 * N - 5; i++)
  31.         fac[i] = fac[i - 1] * i % mod;
  32.     inv[2 * N - 5] = Exp(fac[2 * N - 5], mod - 2);
  33.     for (int i = 2 * N - 6; i >= 0; i--)
  34.         inv[i] = inv[i + 1] * (i + 1) % mod;
  35.     cin >> n >> k;
  36.     dp[0][0] = 1;
  37.     f[0][0] = 1;
  38.     for (int i = 1; i <= min(n, B - 5); i++) {
  39.         for (int j = 1; j <= k; j++) {
  40.             if (j >= i) add(dp[i][j], (dp[i][j - i] + dp[i - 1][j - i]) % mod);
  41.             if (j >= n + 1) dp[i][j] = (dp[i][j] - dp[i - 1][j - n - 1] + mod) % mod;
  42.             add(f[i & 1][j], dp[i][j]);
  43.         }
  44.     }
  45.     ll ans = 0;
  46.     for (int i = 0; i <= k; i++) {
  47.         add(ans, Euler(k - i, n) * (f[0][i] - f[1][i] + mod) % mod);
  48.     }
  49.     cout << ans;
  50. }
  51. /*
  52. dua bai toan ve tim so day a[] sao cho a[i] < i va tong day = k
  53. - ta dem so day bang bao ham loai tru :
  54. mot day khong thoa man khi ton tai a[i] >= i
  55. nhu vay neu ta nhin duoi dang bitmask n phan tu voi phan tu i bat <=> a[i] >= i bai toan se tro ve bai dem so so nguyen to cung nhau voi x
  56. xet day gom n phan tu a[i] = i, goi dp[i][j] la so cach de tao ra tong j tu i phan tu trong day a[], goi f[0/1][j] lan luot la so cach tao ra tong j tu chan / le phan tu trong day a[]
  57. tu day ta co cong thuc ans = tong (chiakeo(k - x, n) * (f[0][x] - f[1][x]) voi moi 0 <= x <= k)
  58. ** cach tinh mang dp **
  59. cong thuc : dp[i][j] = dp[i][j - i] + dp[i - 1][j - i] - dp[i - 1][j - (n + 1)];
  60. dp[i][j - i] -> dp[i][j] la dat mot thanh nam ngang do dai i duoi i phan tu dang co
  61. dp[i - 1][j - i] -> dp[i][j] la dat mot thanh nam ngang do dai i + 1 duoi i phan tu dang co va tao ra them phan tu thu i + 1
  62. - dp[i - 1][j - (n + 1)] la de loai di cac trang thai ma sau khi dat cac thanh ngang thi xuat hien phan tu lon nhat = (n + 1) (cac phan tu nay bi loai vi day a[] co a[i] = i)
  63. */
  64.  
Success #stdin #stdout 0.01s 8176KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/u56LXz
language:
C++ (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!