結果
| 問題 |
No.3004 ヤング図形
|
| ユーザー |
 横山緑
|
| 提出日時 | 2025-01-17 23:32:04 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 298 ms / 4,000 ms |
| コード長 | 9,148 bytes |
| コンパイル時間 | 5,224 ms |
| コンパイル使用メモリ | 322,140 KB |
| 実行使用メモリ | 51,292 KB |
| 最終ジャッジ日時 | 2025-01-17 23:32:26 |
| 合計ジャッジ時間 | 14,024 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 25 |
ソースコード
#line 2 "template.hpp"
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// https://xn--kst.jp/blog/2019/08/29/cpp-comp/
// debug methods
// usage: debug(x,y);
// vector 出力できるように修正
template <typename T>
ostream& debug_print(ostream& os, const vector<T>& v) {
os << "[";
for (size_t i = 0; i < v.size(); ++i) {
os << v[i];
if (i < v.size() - 1) os << ", ";
}
os << "]";
return os;
}
template <typename T>
ostream& debug_print(ostream& os, const T& var) {
os << var;
return os;
}
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) { cout << #x1 << ": "; debug_print(cout, x1) << endl; }
#define debug_2(x1, x2) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << endl; }
#define debug_3(x1, x2, x3) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << endl; }
#define debug_4(x1, x2, x3, x4) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << endl; }
#define debug_5(x1, x2, x3, x4, x5) { cout << #x1 << ": "; debug_print(cout, x1) << ", " << #x2 << ": "; debug_print(cout, x2) << ", " << #x3 << ": "; debug_print(cout, x3) << ", " << #x4 << ": "; debug_print(cout, x4) << ", " << #x5 << ": "; debug_print(cout, x5) << endl; }
#ifdef LOCAL
#define debug(...) CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~))(__VA_ARGS__)
#else
#define debug(...)
#endif
using ll = long long;
using vl = vector<ll>;
using Graph = vector<vector<ll>>;
using P = pair<ll, ll>;
#define all(v) v.begin(), v.end()
template <typename T> inline bool chmax(T &a, T b) {
return ((a < b) ? (a = b, true) : (false));
}
template <typename T> inline bool chmin(T &a, T b) {
return ((a > b) ? (a = b, true) : (false));
}
#define rep1(i, n) for(ll i = 1; i <= ((ll)n); ++i)
// https://trap.jp/post/1224/
template <class... T> constexpr auto min(T... a) {
return min(initializer_list<common_type_t<T...>>{a...});
}
template <class... T> constexpr auto max(T... a) {
return max(initializer_list<common_type_t<T...>>{a...});
}
template <class... T> void input(T &...a) { (cin >> ... >> a); }
template <class T> void input(vector<T> &a) {
for(T &x : a)
cin >> x;
}
void print() { cout << '\n'; }
template <class T, class... Ts> void print(const T &a, const Ts &...b) {
cout << a;
(cout << ... << (cout << ' ', b));
cout << '\n';
}
void print(const string &s) {
cout << s << '\n';
}
template <class Container, typename = void>
struct is_container : std::false_type {};
template <class Container>
struct is_container<Container, std::void_t<decltype(std::declval<Container>().begin()), decltype(std::declval<Container>().end())>> : std::true_type {};
template <class Container>
typename enable_if<is_container<Container>::value>::type print(const Container& x) {
if (!x.empty()) {
auto it = x.begin();
for (; it != prev(x.end()); ++it) {
cout << *it << " ";
}
cout << *it << "\n"; // 最後の要素を出力して改行
}
}
#define INT(...) \
int __VA_ARGS__; \
input(__VA_ARGS__)
#define LL(...) \
long long __VA_ARGS__; \
input(__VA_ARGS__)
#define STR(...) \
string __VA_ARGS__; \
input(__VA_ARGS__)
#define REP1(a) for(ll i = 0; i < a; i++)
#define REP2(i, a) for(ll i = 0; i < a; i++)
#define REP3(i, a, b) for(ll i = a; i < b; i++)
#define REP4(i, a, b, c) for(ll i = a; i < b; i += c)
#define overload4(a, b, c, d, e, ...) e
#define rep(...) overload4(__VA_ARGS__, REP4, REP3, REP2, REP1)(__VA_ARGS__)
ll inf = 3e18;
vl dx = {1, -1, 0, 0};
vl dy = {0, 0, 1, -1};
#line 3 "math/factorial.hpp"
// https://suisen-cp.github.io/cp-library-cpp/library/math/factorial.hpp
template <class T> struct factorial {
factorial() {};
void ensure(const int n) {
int sz = size(fac);
if(sz > n) {
return;
}
int new_sz = max(2 * sz, n + 1);
fac.resize(new_sz), fac_inv.resize(new_sz);
for(int i = sz; i < new_sz; i++) {
if(i == 0) {
fac[i] = 1;
continue;
}
fac[i] = fac[i - 1] * i;
}
fac_inv[new_sz - 1] = T(1) / fac[new_sz - 1];
for(int i = new_sz - 2; i >= sz; i--) {
fac_inv[i] = fac_inv[i + 1] * (i + 1);
}
return;
}
T get(int i) {
ensure(i);
return fac[i];
}
T operator[](int i) { return get(i); }
T inv(int i) {
ensure(i);
return fac_inv[i];
}
T binom(int n, int i) {
if(n < 0 || i < 0 || n < i) {
return T(0);
}
ensure(n);
return fac[n] * fac_inv[i] * fac_inv[n - i];
}
T perm(int n, int i) {
if(n < 0 || i < 0 || n < i) {
return T(0);
}
ensure(n);
return fac[n] * fac_inv[n - i];
}
private:
vector<T> fac, fac_inv;
};
#line 3 "poly/shift_of_sampling_points.hpp"
#include <atcoder/convolution>
// https://suisen-cp.github.io/cp-library-cpp/library/polynomial/shift_of_sampling_points.hpp
template <class Mint>
vector<Mint> shift_of_sampling_points(const vector<Mint> &f, const int m,
const int c) {
// n次未満の多項式fのn個の点f(0),...,f(n-1)に対して
// f(c),...,f(c+m-1)を計算
factorial<Mint> fac;
const int n = f.size();
auto a = [&] {
vector<Mint> a1(n), a2(n);
rep(i, n) {
a1[i] = f[i] * fac.inv(i);
a2[i] = ((i & 1) ? -1 : 1) * fac.inv(i);
}
auto a = convolution(a1, a2);
a.resize(n);
return a;
}();
vector<Mint> a_(n);
rep(i, n) { a_[i] = a[n - 1 - i] * fac[n - 1 - i]; }
vector<Mint> b2 = [&] {
// b2[i] = c*(c-1)*...*(c-i+1)/i!
vector<Mint> b2(n);
Mint ci = 1;
b2[0] = ci;
for(int i = 1; i < n; i++) {
ci *= c - i + 1;
b2[i] = ci * fac.inv(i);
}
return b2;
}();
auto b = convolution(a_, b2);
vector<Mint> fc = [&] {
vector<Mint> f1(n);
vector<Mint> f2(m);
rep(i, n) { f1[i] = b[n - 1 - i] * fac.inv(i); }
rep(i, m) { f2[i] = fac.inv(i); }
return convolution(f1, f2);
}();
vector<Mint> res(m);
rep(i, m) { res[i] = fac[i] * fc[i]; }
return res;
}
#line 4 "math/factorial_large.hpp"
#include <atcoder/modint>
template <class mint> struct factorial_large {
const ll K = 9;
vector<vector<mint>> f;
vector<mint> g;
factorial_large() {
// f_i(x) = (2^i x + 1) * ... * (2^i x + 2^i - 1)
// f_i(0) , ... , f_i(2^i - 1) の値が分かればシフトできる
f = vector(K + 1, vector<mint>());
f[0] = {1};
// f_0(x) = 1
rep(i, K) {
// cul f_(i+1)
ll ti = 1LL << i;
auto f1 = shift_of_sampling_points<mint>(f[i], 3 * ti, ti);
f[i].insert(f[i].end(), all(f1));
f[i + 1].resize(2 * ti);
rep(j, 2 * ti) {
f[i + 1][j] = f[i][2 * j] * f[i][2 * j + 1] * ti * (2 * j + 1);
}
}
// g_i = (i*2^K)!
{
ll sz = ll(mint::mod()) / (1LL << K) + 1;
auto g1 = shift_of_sampling_points(f[K], sz - 1, 0);
g.resize(sz);
g[0] = 1;
mint tK = 1 << K;
for(int i = 1; i < sz; i++) {
g[i] = g[i - 1] * g1[i - 1] * tK * i;
}
}
}
mint fac(ll n) {
if(n >= mint::mod())
return 0;
ll r = n / (1LL << K);
ll q = n - (1LL << K) * r;
mint res = g[r];
for(ll i = (1LL << K) * r + 1; i <= n; i++) {
res *= i;
}
return res;
}
};
#line 5 "/home/y_midori/cp/yukicoder/455/c.cpp"
// using namespace atcoder;
using mint = atcoder::modint998244353;
factorial<mint> fac;
factorial_large<mint> fac_large;
mint cul_fac(ll n) {
if(n < 1e6) {
return fac[n];
} else
return fac_large.fac(n);
}
void solve() {
LL(k);
ll sum = 0;
mint ans = 1;
rep(i, k) {
LL(l, m);
sum += l * m;
ans *= cul_fac(m).inv();
ans *= cul_fac(l).inv().pow(m);
}
ans *= cul_fac(sum);
print(ans.val());
}
int main() {
ios::sync_with_stdio(false);
std::cin.tie(nullptr);
cout << std::setprecision(16);
int t = 1;
rep(_, t) {
solve();
}
}