提出 #42727056

---

ソースコード 拡げる

#ifdef LOCAL
class SS {
   int x[0];
};
extern "C" SS __sanitizer_print_stack_trace();
#define __last_state                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   }                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   ;                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   \
   SS x {                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                              \
      __sanitizer_print_stack_trace()
#endif
#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <math.h>

using namespace __gnu_pbds;
using namespace std;
#define endl "\n"
#define mp make_pair
#define st first
#define nd second
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0);
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define fwd(i, a, b) for (int i = (a); i < (b); ++i)
#define trav(a, x) for (auto &a : x)
#define all(c) (c).begin(), (c).end()
#define sz(X) (int)((X).size())
typedef long double ld;
typedef unsigned long long ull;
typedef long long ll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; // find_by_order(x) <-returns x-th element   order_of_key(x) <- returns order of element x
// mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());uniform_int_distribution<int> distr(0, 1e9);auto my_rand = bind(distr, gen); // my_rand() zwraca teraz liczbe z przedzialu [a, b]
#ifdef LOCAL
ostream &operator<<(ostream &out, string str) {
   for (char c : str)
      out << c;
   return out;
}
template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
template <class L, class R, class S> ostream &operator<<(ostream &out, tuple<L, R, S> p) {
   auto &[a, b, c] = p;
   return out << "(" << a << ", " << b << ", " << c << ")";
}
template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
   out << '{';
   for (auto it = a.begin(); it != a.end(); it = next(it))
      out << (it != a.begin() ? ", " : "") << *it;
   return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) ;
#endif

namespace MATH {

   const ll mod = 998244353;

   ull mod_mul(ull a, ull b, ull M) {
      ll ret = a * b - M * ull(ld(a) * ld(b) / ld(M));
      return ret + M * (ret < 0) - M * (ret >= (ll)M);
   }

   ull mod_pow(ull b, ull e, ull mod) {
      ull ans = 1;
      for (; e; b = mod_mul(b, b, mod), e /= 2)
         if (e & 1)
            ans = mod_mul(ans, b, mod);
      return ans;
   }

   ull mod_mul(ull a, ull b) { return mod_mul(a, b, mod); }
   ull mod_pow(ull a, ull b) { return mod_pow(a, b, mod); }
   ull inv(ull a) { return mod_pow(a, mod - 2, mod); }

   ull pollard(ull n) {
      auto f = [n](ull x) { return (mod_mul(x, x, n) + 1) % n; };
      if (!(n & 1))
         return 2;
      for (ull i = 2;; i++) {
         ull x = i, y = f(x), p;
         while ((p = __gcd(n + y - x, n)) == 1)
            x = f(x), y = f(f(y));
         if (p != n)
            return p;
      }
   }

   bool isPrime(ull n) {
      if (n < 2 || n % 6 % 4 != 1)
         return n - 2 < 2;
      ull A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022}, s = __builtin_ctzll(n - 1), d = n >> s;
      for (int a : A) {
         ull p = mod_pow(a, d, n), i = s;
         while (p != 1 && p != n - 1 && a % n && i--)
            p = mod_mul(p, p, n);
         if (p != n - 1 && i != s)
            return 0;
      }
      return 1;
   }

   vector<ull> factor(ull n) {
      if (n == 1)
         return {};
      if (isPrime(n))
         return {n};
      ull x = pollard(n);
      auto l = factor(x), r = factor(n / x);
      l.insert(l.end(), all(r));
      return l;
   }

   const int MAXF = 510;
   const int MAXN = MAXF;
   ll F[MAXF], I[MAXF];
   ll B[MAXN][MAXN];
   ll binom(int a, int b) { return mod_mul(mod_mul(F[a], I[b]), I[a - b]); }

   void pre() {
      F[0] = I[0] = 1;
      for (int i = 1; i < MAXF; i++) {
         F[i] = mod_mul(i, F[i - 1]);
         I[i] = inv(F[i]);
      }
      rep(i, MAXF) rep(j, MAXF) B[i][j] = binom(i, j);
   }

} // namespace MATH

#define int long long

constexpr int mod = 998244353;
const int MAXN = 502;
int32_t dp[MAXN][MAXN][MAXN];
int X[MAXN];

int32_t main() {
   _upgrade;

   MATH::pre();
   const int T = 500;

   int n = T;
   cin >> n;
   rep(i, n) {
      int a = T;
      cin >> a;
      rep(i, a + 1) X[i]++;
   }

   dp[0][MAXN - 1][0] = 1;

   rep(wartosci, MAXN) rep(maks, MAXN) rep(pola, MAXN) if (dp[wartosci][maks][pola]) {
      rep(maks2, maks) {
         int A = dp[wartosci][maks][pola];
         int dostepne = X[maks2];
         int dostepne_wartosci = dostepne - wartosci;
         int dostpne_pola = dostepne - pola;
         for (int ile = 1; ile < MAXN; ile++) {
            int ile_pol = maks2 * ile;
            if (dostpne_pola < ile_pol or dostepne_wartosci < ile)
               break;

            A = (A * MATH::B[dostpne_pola - (ile - 1) * maks2][maks2]) % mod;
            int B = MATH::B[dostepne_wartosci][ile];

            // dp[wartosci + ile][maks2][pola + ile_pol] += A * B;

            dp[wartosci + ile][maks2][pola + ile_pol] = (dp[wartosci + ile][maks2][pola + ile_pol] + A * B) % mod;
         }
      }
   }
   // rep(i, 4) rep(j, 4) rep(l, 4) if (dp[i][j][l]) debug(i, j, l, dp[i][j][l]);

   int res = 0;
   rep(maks, MAXN) res += dp[n][maks][n];
   cout << (res % mod) << endl;
}

提出情報

ジャッジ結果