oj.uz

Submission #960154

# Submission time Handle Problem Language Result Execution time Memory
960154 2024-04-09T18:33:06 Z Pety Magneti (COCI21_magneti) C++17
0 / 110
 117 ms 106324 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6+2;
const int mod = 1e9 + 7;
template <class T> T pow(T a, int64_t exp) {
  T res(1);
  while (exp) {
    if (exp % 2)
      res = res * a;
    a = a * a;
    exp /= 2;
  }
  return res;
}

template <decltype(auto) mode> struct ZP;
using ZPP = ZP<mod>;
template <decltype(auto) mod, decltype(auto) R> struct Poly {
  using ZPP = ZP<mod>;

  Poly(ZPP x = 0) : A(0), B(x) {}
  Poly(ZPP A, ZPP B) : A(A), B(B) {}

  Poly operator*(Poly that) const {
    ZPP a = A * that.A;
    ZPP b = A * that.B + B * that.A;
    ZPP c = B * that.B;
    return Poly(b, c + a * R);
  }

  ZPP A, B;
};

template <decltype(auto) mod> struct ZP {
  ZP(int64_t x = 0) : x(x % mod) {
    if (this->x < 0)
      this->x += mod;
  }

  ZP operator*(ZP that) const { return ZP(int64_t(x) * that.x); }
  ZP &operator+=(ZP that) {
    if ((x += that.x) >= mod)
      x -= mod;
    return *this;
  }
  ZP operator-=(ZP that) {
    if ((x -= that.x) < 0)
      x += mod;
    return *this;
  }
  ZP operator*=(ZP that) { return *this = *this * that; }

  ZP operator-(ZP that) const { return ZP(*this) -= that; }
  ZP operator+(ZP that) const { return ZP(*this) += that; }
  ZP operator-() const { return ZP(mod - x); }
  bool operator==(ZP that) const { return x == that.x; }
  bool operator!=(ZP that) const { return x != that.x; }
  friend ZP operator+(int x, ZP that) { return ZP(x) + that; }
  friend ZP operator-(int x, ZP that) { return ZP(x) - that; }
  ZP operator/(ZP that) const { return *this * that.inv(); }

  ZP inv() const { return pow(*this, mod - 2); }
  explicit operator int() const { return x; }
  explicit operator bool() const { return x; }

  friend ostream &operator<<(ostream &stream, ZP that) {
    return stream << that.x;
  }
  bool operator<(ZP that) const { return x < that.x; }

  optional<ZP> sqrt() {
    if (x < 2) {
      return *this;
    }

    if (pow(*this, (mod - 1) / 2) == -1)
      return nullopt;

    static mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

    while (true) {
      ZP z = rnd();
      if (z * z == *this)
        return z;

      static ZP value;
      value = *this;
      Poly<(mod), (value)> P(1, z);
      P = pow(P, mod / 2);
      if (P.A != 0) {
        assert(P.A.inv() * P.A.inv() == *this);
        return P.A.inv();
      }
    }
  }

  int x;
};

ZPP dp[52][52][10002];
ZPP fact[10100];
int n, l, a[52];

ZPP comb (int n, int k) {
  return fact[n] / fact[k] / fact[n - k];
}
 
int main () 
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> l;
  for (int i = 1; i <= n; i++)
    cin >> a[i];
  fact[0] = 1;
  for (int i = 1; i <= l + n; i++)
    fact[i] = fact[i - 1] * i;
  sort(a + 1, a + n + 1);
  dp[0][0][1] = 1;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= n; j++)
      for (int k = 0; k <= l; k++) {
        dp[i + 1][j + 1][k] += dp[i][j][k];
        if (j && k + a[i + 1] <= l)
          dp[i + 1][j][k + a[i + 1]] += dp[i][j][k];
        if (j > 1 && k + 2 * a[i + 1] <= l)
          dp[i + 1][j - 1][k + 2 * a[i + 1]] += dp[i][j][k];
      }
  }
  ZPP ans = 0;
  for (int d = 1; d <= l; d++) {
    ans += comb(l - d + n, n) * dp[n][1][d];
  }
  cout << ans;
  return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 106320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 37 ms 106324 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 106320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 117 ms 106320 KB Output isn't correct
2 Halted 0 ms 0 KB -