結果
問題 | No.2457 Stampaholic (Easy) |
ユーザー | karinohito |
提出日時 | 2023-09-01 23:27:04 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 538 ms / 4,000 ms |
コード長 | 3,446 bytes |
コンパイル時間 | 4,402 ms |
コンパイル使用メモリ | 266,636 KB |
実行使用メモリ | 31,928 KB |
最終ジャッジ日時 | 2023-09-01 23:27:18 |
合計ジャッジ時間 | 6,868 ms |
ジャッジサーバーID (参考情報) |
judge16 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 147 ms
11,088 KB |
testcase_02 | AC | 16 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,376 KB |
testcase_04 | AC | 2 ms
4,380 KB |
testcase_05 | AC | 135 ms
4,376 KB |
testcase_06 | AC | 7 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 17 ms
4,380 KB |
testcase_09 | AC | 10 ms
4,380 KB |
testcase_10 | AC | 24 ms
4,376 KB |
testcase_11 | AC | 34 ms
4,380 KB |
testcase_12 | AC | 50 ms
4,376 KB |
testcase_13 | AC | 69 ms
4,376 KB |
testcase_14 | AC | 108 ms
4,376 KB |
testcase_15 | AC | 133 ms
4,380 KB |
testcase_16 | AC | 133 ms
4,376 KB |
testcase_17 | AC | 538 ms
31,928 KB |
testcase_18 | AC | 22 ms
4,376 KB |
testcase_19 | AC | 1 ms
4,376 KB |
testcase_20 | AC | 2 ms
4,376 KB |
testcase_21 | AC | 5 ms
4,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vvvvll = vector<vvvll>; using vvvvvll = vector<vvvvll>; #define all(A) A.begin(),A.end() #define rep(i, n) for (ll i = 0; i < (ll) (n); i++) template<class T> bool chmax(T& p, T q, bool C = 1) { if (C == 0 && p == q) { return 1; } if (p < q) { p = q; return 1; } else { return 0; } } template<class T> bool chmin(T& p, T q, bool C = 1) { if (C == 0 && p == q) { return 1; } if (p > q) { p = q; return 1; } else { return 0; } } ll gcd(ll(a), ll(b)) { if (a == 0)return b; if (b == 0)return a; ll c = a; while (a % b != 0) { c = a % b; a = b; b = c; } return b; } ll sqrtz(ll N) { ll L = max(0ll, ll(sqrt(N) - 20)); ll R = sqrt(N) + 20; while (abs(R - L) > 1) { ll mid = (R + L) / 2; if (mid * mid <= N)L = mid; else R = mid; } return L; } ll inva(ll N, ll M) { ll mod = M; ll a = N, b = mod, c = 1, d = 0; while (b > 0) { ll t = a / b; a -= t * b; swap(a, b); c -= t * d; swap(c, d); } c %= mod; if (c < 0)c += mod; return c; } const ll mod = 998244353; ll modPow(long long a, long long n, long long p = mod) { if (n == 0) return 1; // 0乗にも対応する場合 if (n == 1) return a % p; if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p; long long t = modPow(a, n / 2, p); return (t * t) % p; } using mint = modint998244353; mint sum(mint a, mint d, ll n) { if (n < 0)return 0; return (a + (n - 1) * d) / 2 * mint(n); } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); ll H, W, N, K; cin >> H >> W >> N >> K; if (H > W)swap(H, W); mint an = 0; mint al = (H - K + 1) * (W - K + 1); mint alp = al.pow(N); if (W < 2 * K) { vvll P(H, vll(W)); rep(h, H)rep(w, W) { P[h][w] = (min(h, H - K) - max(0ll, h - K + 1) + 1) * (min(w, W - K) - max(0ll, w - K + 1) + 1); an += alp - mint(al - P[h][w]).pow(N); } an /= alp; cout << an.val() << endl; return 0; } else if (H < 2 * K) { mint ZH = mint(H - (K - 1) * 2); mint ZW = mint(W - (K - 1) * 2); rep(h, H) { ll ah = (min(h, H - K) - max(0ll, h - K + 1) + 1); for (ll w = 1; w <= K - 1; w++) { an += 2 * (alp - (mint(al - ah * w).pow(N))); } an += ZW * (alp - (mint(al - ah * K).pow(N))); } an /= alp; cout << an.val() << endl; return 0; } else { mint ZH = mint(H - (K - 1) * 2); mint ZW = mint(W - (K - 1) * 2); for (ll h = 1; h <= K - 1; h++)for (ll w = 1; w <= K - 1; w++) { an += 4 * (alp - (mint(al - h * w).pow(N))); } an += ZH * ZW * (alp - (mint(al - K * K).pow(N))); for (ll h = 1; h <= K - 1; h++) { an += 2 * ZW * (alp - (mint(al - h * K).pow(N))); } for (ll w = 1; w <= K - 1; w++) { an += 2 * ZH * (alp - (mint(al - w * K).pow(N))); } an /= alp; cout << an.val() << endl; return 0; } }