結果

問題 No.2459 Stampaholic (Hard)
ユーザー 👑 NachiaNachia
提出日時 2023-08-25 04:32:11
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 727 ms / 4,000 ms
コード長 2,860 bytes
コンパイル時間 2,484 ms
コンパイル使用メモリ 120,752 KB
実行使用メモリ 34,100 KB
最終ジャッジ日時 2024-06-06 05:06:49
合計ジャッジ時間 11,293 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 710 ms
34,100 KB
testcase_02 AC 162 ms
10,060 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 1 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 336 ms
16,448 KB
testcase_09 AC 162 ms
10,448 KB
testcase_10 AC 707 ms
32,192 KB
testcase_11 AC 356 ms
18,044 KB
testcase_12 AC 716 ms
33,584 KB
testcase_13 AC 712 ms
31,904 KB
testcase_14 AC 167 ms
11,084 KB
testcase_15 AC 720 ms
33,980 KB
testcase_16 AC 721 ms
33,900 KB
testcase_17 AC 720 ms
33,848 KB
testcase_18 AC 727 ms
33,844 KB
testcase_19 AC 710 ms
33,844 KB
testcase_20 AC 2 ms
6,940 KB
testcase_21 AC 691 ms
30,708 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <atcoder/modint>
#include <atcoder/convolution>
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;

vector<Modint> invfps(vector<Modint> x, int n){
    Modint ix0 = x[0].inv();
    for(auto& a : x) a *= ix0;
    vector<Modint> res;
    res.push_back(1);
    int z = 1;
    while(z < n){
        if((int)x.size() < z*2) x.resize(z*2);
        auto xx = vector(x.begin(), x.begin() + z*2);
        auto tmp = atcoder::convolution(res, xx);
        tmp.resize(z*2);
        tmp = atcoder::convolution(tmp, res);
        rep(i,z) res.push_back(-tmp[z+i]);
        z *= 2;
    }
    for(auto& a : res) a *= ix0;
    return vector(res.begin(), res.begin() + z);
}

vector<Modint> factorial;
vector<Modint> invFactorial;
void extend(int n){
    factorial.resize(1+n);
    factorial[0] = 1;
    for(int i=1; i<=n; i++) factorial[i] = factorial[i-1] * i;
    invFactorial.resize(1+n);
    invFactorial[n] = factorial[n].inv();
    for(int i=n; i>=1; i--) invFactorial[i-1] = invFactorial[i] * i;
}
Modint comb(int n, int k){ return factorial[n] * invFactorial[k] * invFactorial[n-k]; }

vector<Modint> powsum(Modint q, int n){
    vector<Modint> a(n+1), b(n+1);
    a[0] = q; rep(i,n) a[i+1] = a[i] * q;
    rep(i,n+1) a[i] *= invFactorial[i+1];
    rep(i,n+1) b[i] = invFactorial[i+1];
    auto invb = invfps(move(b), n+1);
    a = atcoder::convolution(a, invb);
    rep(i,n+1) a[i] *= factorial[i];
    return vector(a.begin(), a.begin() + (n+1));
}

int main(){
    i64 H, W, N, K; cin >> H >> W >> N >> K;
    extend(N+2);
    i64 f = (H-K+1) * (W-K+1);
    Modint p = (Modint(f)).inv().pow(N);
    Modint ans = 0;
    i64 xcent = min(K, W-K+1);
    i64 xcent_width = W - xcent * 2 + 2;
    i64 ycent = min(K, H-K+1);
    i64 ycent_width = H - ycent * 2 + 2;
    auto xpowsum = powsum(xcent, N); xpowsum[0] -= 1;
    auto ypowsum = powsum(ycent, N); ypowsum[0] -= 1;
    vector<Modint> powf(N+1);
    powf[0] = Modint((N%2==0) ? 1 : -1);
    rep(i,N) powf[i+1] = powf[i] * (-f);
    vector<Modint> pow_xcent(N+1);
    pow_xcent[0] = 1;
    rep(i,N) pow_xcent[i+1] = pow_xcent[i] * xcent;
    vector<Modint> pow_ycent(N+1);
    pow_ycent[0] = 1;
    rep(i,N) pow_ycent[i+1] = pow_ycent[i] * ycent;
    rep(k,N+1) ans += comb(N,k) * powf[N-k] * (xpowsum[k] * 2 + pow_xcent[k] * xcent_width) * (ypowsum[k] * 2 + pow_ycent[k] * ycent_width);
    ans *= p;
    ans = Modint(H*W) - ans;
    cout << ans.val() << endl;
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0