fork(1) download
copy 
  1. // author: Lien
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. #define rep(i, a, b) for (int i = a; i < (b); ++i)
  6. #define sz(s) (int)(s).size()
  7. #define all(x) begin(x), end(x)
  8. #define trav(x, v) for (const auto &x : v)
  9.  
  10. using i64 = long long;
  11. using vi = vector<int>;
  12. using pii = pair<int, int>;
  13. using vpi = vector<pii>;
  14.  
  15. vi get_coef(const vi &a, int mod) {
  16.     // coef[sum(mask)] += sum(a(mask)) * (popcount(mask) % 2 == 1 ? 1 : -1)
  17.     // O(sum * N)
  18.     int sum = accumulate(all(a), 0);
  19.     vector<vi> dp(2, vi(sum + 1, 0));
  20.     dp[0][0] = 1;
  21.     trav(v, a) {
  22.         for (int s = sum; s >= v; --s) {
  23.             dp[0][s] += dp[1][s - v];
  24.             dp[1][s] += dp[0][s - v];
  25.         }
  26.     }
  27.     vi coef(sum, 0);
  28.     rep(s, 0, sum) {
  29.         coef[s] = (dp[1][s + 1] - dp[0][s + 1]) % mod;
  30.         if (coef[s] < 0) coef[s] += mod;
  31.     }
  32.     return coef;
  33. }
  34.  
  35. vi get_f(const vi& a, int mod) {
  36.     // first sum(a_i) term [0, sum) = number of solutions for case [0..sum-1]
  37.     // O(sum * N)
  38.     int sum = accumulate(all(a), 0);
  39.     vi f(sum, 0);
  40.     f[0] = 1;
  41.     trav(v, a) {
  42.         rep(s, v, sum) {
  43.             f[s] += f[s - v];
  44.             if (f[s] >= mod) f[s] -= mod;
  45.         }
  46.     }
  47.     return f;
  48. }
  49.  
  50. int get_mth(const vi &coef, const vi &f, i64 m, int mod) {
  51.     // Team Note of Deobureo Minkyu Party
  52.     // f[k] = f[k - 1] * coef[m - 1] + f[k - 2] * coef[m - 2] + .. + f[k - m] * coef[0]
  53.     // O(N^2 * logM), can improved to O(N * logN * logM) by using FFT
  54.     int n = sz(coef);
  55.     if (m < n) return f[(int)m];
  56.     vi s(n), t(n);
  57.     s[0] = 1;
  58.     if (n != 1) t[1] = 1;
  59.     else t[0] = coef[0];
  60.  
  61.     auto mul = [&n, &coef, &mod](const vi &v, const vi &w) {
  62.         // todo: fft
  63.         vi t(2 * n);
  64.         rep(j, 0, n) rep(k, 0, n) {
  65.             t[j + k] += 1LL * v[j] * w[k] % mod;
  66.             if (t[j + k] >= mod) t[j + k] -= mod;
  67.         }
  68.         for (int j = 2 * n - 1; j >= n; --j)
  69.         for (int k = 1; k <= n; ++k) {
  70.             t[j - k] += 1LL * t[j] * coef[k - 1] % mod;
  71.             if (t[j - k] >= mod) t[j - k] -= mod;
  72.         }
  73.         t.resize(n);
  74.         return t;
  75.     };
  76.  
  77.     for (; m > 0; m >>= 1) {
  78.         if (m & 1) s = mul(s, t);
  79.         t = mul(t, t);
  80.     }
  81.  
  82.     i64 ret = 0;
  83.     rep(i, 0, n) ret += 1LL * s[i] * f[i] % mod;
  84.     return ret % mod;
  85. }
  86.  
  87. int main() {
  88.     ios::sync_with_stdio(false);
  89.     cin.tie(0);
  90.  
  91.     int n;
  92.     i64 m;
  93.     cin >> n >> m;
  94.     vi a(n);
  95.     for (auto &v : a) cin >> v;
  96.  
  97.     constexpr int MOD = int(1e9) + 7;
  98.     vi coef = get_coef(a, MOD);
  99.     vi f = get_f(a, MOD);
  100.     cout << get_mth(coef, f, m, MOD) << '\n';
  101.     return 0;
  102. }
  103.  
  104. // 3 * x_0 + 3 * x_1 + 6 * x_2 + 11 * x_3 = 100000
  105. // a = {3, 3, 6, 11} -> n = 4
  106. // m = 10^5
  107. // answer = 587812715
Success #stdin #stdout 0s 4196KB
comments (?)
stdin
copy 
4 100000
3 3 6 11
stdout
copy 
587812715
https://ideone.com/BDwZW6
4 100000
3 3 6 11
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
secret

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!