Submission #960156

#	Time	Username	Problem	Language	Result	Execution time	Memory
960156		Pety	Magneti (COCI21_magneti)	C++17	110 / 110	246 ms	106580 KiB

Main

#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] += ZPP (j + 1) * dp[i][j][k];
        if (j && k + a[i + 1] <= l)
          dp[i + 1][j][k + a[i + 1]] += ZPP(2*j)*dp[i][j][k];
        if (j > 1 && k + 2 * a[i + 1] <= l)
          dp[i + 1][j - 1][k + 2 * a[i + 1]] += ZPP(j - 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: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50