結果
| 問題 | No.2459 Stampaholic (Hard) |
| ユーザー |
 Forested
|
| 提出日時 | 2023-09-01 23:44:25 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,767 bytes |
| コンパイル時間 | 3,345 ms |
| コンパイル使用メモリ | 174,452 KB |
| 実行使用メモリ | 35,172 KB |
| 最終ジャッジ日時 | 2024-06-11 05:58:15 |
| 合計ジャッジ時間 | 8,444 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
5,248 KB |
| testcase_01 | AC | 386 ms
35,172 KB |
| testcase_02 | AC | 85 ms
9,852 KB |
| testcase_03 | WA | - |
| testcase_04 | AC | 2 ms
5,376 KB |
| testcase_05 | AC | 2 ms
5,376 KB |
| testcase_06 | AC | 2 ms
5,376 KB |
| testcase_07 | AC | 2 ms
5,376 KB |
| testcase_08 | WA | - |
| testcase_09 | AC | 88 ms
10,720 KB |
| testcase_10 | WA | - |
| testcase_11 | AC | 186 ms
18,524 KB |
| testcase_12 | WA | - |
| testcase_13 | AC | 378 ms
31,284 KB |
| testcase_14 | AC | 93 ms
11,312 KB |
| testcase_15 | WA | - |
| testcase_16 | WA | - |
| testcase_17 | AC | 389 ms
35,168 KB |
| testcase_18 | AC | 380 ms
35,168 KB |
| testcase_19 | AC | 392 ms
35,108 KB |
| testcase_20 | WA | - |
| testcase_21 | WA | - |
ソースコード
#ifndef LOCAL
#define FAST_IO
#endif
// ============
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, m, n) for (i32 i = (i32)(m); i < (i32)(n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32)(n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using i32 = signed int;
using i64 = signed long long;
using f64 = double;
using f80 = long double;
template <typename T>
using Vec = vector<T>;
template <typename T>
bool chmin(T &x, const T &y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
if (x < y) {
x = y;
return true;
}
return false;
}
#ifdef INT128
using u128 = __uint128_t;
using i128 = __int128_t;
istream &operator>>(istream &is, i128 &x) {
i64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, i128 x) {
os << (i64)x;
return os;
}
istream &operator>>(istream &is, u128 &x) {
u64 v;
is >> v;
x = v;
return is;
}
ostream &operator<<(ostream &os, u128 x) {
os << (u64)x;
return os;
}
#endif
[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;
struct SetUpIO {
SetUpIO() {
#ifdef FAST_IO
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cout << fixed << setprecision(15);
}
} set_up_io;
// ============
#ifdef DEBUGF
#else
#define DBG(x) (void)0
#endif
// ============
// ============
#include <algorithm>
#include <iostream>
#include <atcoder/convolution>
namespace poly {
using Mint = atcoder::modint998244353;
using Poly = std::vector<Mint>;
Poly add(Poly f, Poly g) {
if (f.size() < g.size()) {
std::swap(f, g);
}
for (int i = 0; i < (int)g.size(); ++i) {
f[i] += g[i];
}
return f;
}
Poly sub(Poly f, Poly g) {
if (f.size() < g.size()) {
std::swap(f, g);
}
for (int i = 0; i < (int)g.size(); ++i) {
f[i] -= g[i];
}
return f;
}
Poly mul(const Poly &f, const Poly &g) {
return atcoder::convolution(f, g);
}
void dft(Poly &f) {
atcoder::internal::butterfly(f);
}
void idft(Poly &f) {
atcoder::internal::butterfly_inv(f);
int ctz = __builtin_ctz((int)f.size());
Mint inv = Mint::raw(Mint::mod() - (Mint::mod() >> ctz));
for (Mint &cf : f) {
cf *= inv;
}
}
} // namespace poly
// ============
namespace poly {
Poly fps_inv(const Poly &f, int sz = -1) {
assert(!f.empty() && f[0] != Mint());
if (sz == -1) {
sz = (int)f.size();
}
assert(sz >= 0);
Poly g(1, f[0].inv());
while ((int)g.size() < sz) {
Poly fg;
if (2 * g.size() <= f.size()) {
fg = Poly(f.begin(), f.begin() + 2 * g.size());
} else {
fg = f;
fg.resize(2 * g.size());
}
dft(fg);
Poly dft_g = g;
dft_g.resize(2 * g.size());
dft(dft_g);
for (int i = 0; i < (int)dft_g.size(); ++i) {
fg[i] *= dft_g[i];
}
idft(fg);
std::fill(fg.begin(), fg.begin() + g.size(), Mint());
dft(fg);
for (int i = 0; i < (int)dft_g.size(); ++i) {
fg[i] *= dft_g[i];
}
idft(fg);
g.resize(2 * g.size());
for (int i = (int)g.size() / 2; i < (int)g.size(); ++i) {
g[i] = -fg[i];
}
}
g.resize(sz);
return g;
}
} // namespace poly
// ============
// ============
// ============
// ============
namespace poly {
class Factorial {
std::vector<Mint> fac;
std::vector<Mint> ifac;
public:
Factorial() : fac(1, Mint::raw(1)), ifac(1, Mint::raw(1)) {}
void reserve(int n) {
int m = (int)fac.size() - 1;
if (n <= m) {
return;
}
fac.resize(n + 1);
for (int i = m + 1; i <= n; ++i) {
fac[i] = fac[i - 1] * Mint::raw(i);
}
ifac.resize(n + 1);
ifac[n] = fac[n].inv();
for (int i = n - 1; i >= m; --i) {
ifac[i] = ifac[i + 1] * Mint::raw(i + 1);
}
}
Mint fact(int n) const {
assert(n < (int)fac.size());
return fac[n];
}
Mint inv_fact(int n) const {
assert(n < (int)fac.size());
return ifac[n];
}
Mint inv_n(int n) const {
assert(n < (int)fac.size());
return ifac[n] * fac[n - 1];
}
Mint binom(int n, int r) const {
assert(n < (int)fac.size());
return fac[n] * ifac[r] * ifac[n - r];
}
} factorial;
} // namespace poly
// ============
using namespace poly;
Vec<Mint> enumerate_pow_sum(Mint x, i32 deg_max) {
x += Mint(1);
Vec<Mint> f(deg_max + 1), g(deg_max + 1);
Mint p = x;
REP(i, deg_max + 1) {
f[i] = p * factorial.inv_fact(i + 1);
g[i] = factorial.inv_fact(i + 1);
p *= x;
}
Vec<Mint> inv_g = fps_inv(g);
Vec<Mint> f_div_g = mul(f, inv_g);
f_div_g.resize(deg_max + 1);
REP(i, deg_max + 1) {
f_div_g[i] *= factorial.fact(i);
}
return f_div_g;
}
int main() {
i32 h, w, n, k;
cin >> h >> w >> n >> k;
factorial.reserve(n + 10);
Mint sum;
i32 h_max = min({(h + 1) / 2, h - k + 1, k});
i32 w_max = min({(w + 1) / 2, w - k + 1, k});
i32 h_max_cnt = h - 2 * (h_max - 1);
i32 w_max_cnt = w - 2 * (w_max - 1);
Mint tot = Mint(h - k + 1) * Mint(w - k + 1);
Vec<Mint> pow_tot(n + 1, Mint(1)), pow_h_max(n + 1, Mint(1)), pow_w_max(n + 1, Mint(1));
REP(i, n) {
pow_tot[i + 1] = pow_tot[i] * tot;
pow_h_max[i + 1] = pow_h_max[i] * Mint(h_max);
pow_w_max[i + 1] = pow_h_max[i] * Mint(w_max);
}
Vec<Mint> h_side = enumerate_pow_sum(Mint(h_max - 1), n);
Vec<Mint> w_side = enumerate_pow_sum(Mint(w_max - 1), n);
h_side[0] -= Mint(1);
w_side[0] -= Mint(1);
{
Mint cur_sum;
REP(i, n + 1) {
Mint tmp = factorial.binom(n, i) * pow_tot[i] * h_side[n - i] * w_side[n - i];
if ((n - i) % 2 == 0) {
cur_sum += tmp;
} else {
cur_sum -= tmp;
}
}
sum += cur_sum * Mint(4);
}
{
Mint cur_sum;
REP(i, n + 1) {
Mint tmp = factorial.binom(n, i) * pow_tot[i] * h_side[n - i] * pow_w_max[n - i] * Mint(w_max_cnt);
if ((n - i) % 2 == 0) {
cur_sum += tmp;
} else {
cur_sum -= tmp;
}
}
sum += cur_sum * Mint(2);
}
{
Mint cur_sum;
REP(i, n + 1) {
Mint tmp = factorial.binom(n, i) * pow_tot[i] * w_side[n - i] * pow_h_max[n - i] * Mint(h_max_cnt);
if ((n - i) % 2 == 0) {
cur_sum += tmp;
} else {
cur_sum -= tmp;
}
}
sum += cur_sum * Mint(2);
}
{
Mint si = tot - Mint(h_max) * Mint(w_max);
sum += si.pow(n) * Mint(h_max_cnt) * Mint(w_max_cnt);
DBG(sum);
}
sum /= (Mint(h - k + 1) * Mint(w - k + 1)).pow(n);
Mint ans = Mint(h) * Mint(w) - sum;
cout << ans.val() << '\n';
}