Submission #960155

# Submission time Handle Problem Language Result Execution time Memory
960155 2024-04-09T18:35:26 Z Pety Magneti (COCI21_magneti) C++14
Compilation error
0 ms 0 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] += 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;
}

Compilation message

Main.cpp:18:11: error: cannot declare a parameter with 'decltype(auto)'
   18 | template <decltype(auto) mode> struct ZP;
      |           ^~~~~~~~~~~~~~
Main.cpp:19:19: note: invalid template non-type parameter
   19 | using ZPP = ZP<mod>;
      |                   ^
Main.cpp:20:11: error: cannot declare a parameter with 'decltype(auto)'
   20 | template <decltype(auto) mod, decltype(auto) R> struct Poly {
      |           ^~~~~~~~~~~~~~
Main.cpp:20:31: error: cannot declare a parameter with 'decltype(auto)'
   20 | template <decltype(auto) mod, decltype(auto) R> struct Poly {
      |                               ^~~~~~~~~~~~~~
Main.cpp:23:11: error: expected ')' before 'x'
   23 |   Poly(ZPP x = 0) : A(0), B(x) {}
      |       ~   ^~
      |           )
Main.cpp:24:11: error: expected ')' before 'A'
   24 |   Poly(ZPP A, ZPP B) : A(A), B(B) {}
      |       ~   ^~
      |           )
Main.cpp:33:3: error: 'ZPP' does not name a type; did you mean 'ZP'?
   33 |   ZPP A, B;
      |   ^~~
      |   ZP
Main.cpp:36:11: error: cannot declare a parameter with 'decltype(auto)'
   36 | template <decltype(auto) mod> struct ZP {
      |           ^~~~~~~~~~~~~~
Main.cpp:102:1: error: 'ZPP' does not name a type; did you mean 'ZP'?
  102 | ZPP dp[52][52][10002];
      | ^~~
      | ZP
Main.cpp:103:1: error: 'ZPP' does not name a type; did you mean 'ZP'?
  103 | ZPP fact[10100];
      | ^~~
      | ZP
Main.cpp:106:1: error: 'ZPP' does not name a type; did you mean 'ZP'?
  106 | ZPP comb (int n, int k) {
      | ^~~
      | ZP
Main.cpp: In function 'int main()':
Main.cpp:117:3: error: 'fact' was not declared in this scope
  117 |   fact[0] = 1;
      |   ^~~~
Main.cpp:121:3: error: 'dp' was not declared in this scope
  121 |   dp[0][0][1] = 1;
      |   ^~
Main.cpp:125:32: error: 'ZPP' was not declared in this scope; did you mean 'ZP'?
  125 |         dp[i + 1][j + 1][k] += ZPP (j + 1) * dp[i][j][k];
      |                                ^~~
      |                                ZP
Main.cpp:132:3: error: 'ZPP' was not declared in this scope; did you mean 'ZP'?
  132 |   ZPP ans = 0;
      |   ^~~
      |   ZP
Main.cpp:134:5: error: 'ans' was not declared in this scope; did you mean 'abs'?
  134 |     ans += comb(l - d + n, n) * dp[n][1][d];
      |     ^~~
      |     abs
Main.cpp:134:12: error: 'comb' was not declared in this scope; did you mean 'wctomb'?
  134 |     ans += comb(l - d + n, n) * dp[n][1][d];
      |            ^~~~
      |            wctomb
Main.cpp:136:11: error: 'ans' was not declared in this scope; did you mean 'abs'?
  136 |   cout << ans;
      |           ^~~
      |           abs