結果

問題 No.2683 Two Sheets
コンテスト
ユーザー applejam
提出日時 2025-10-02 01:39:09
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 394 ms / 2,000 ms
コード長 1,703 bytes
コンパイル時間 6,009 ms
コンパイル使用メモリ 335,240 KB
実行使用メモリ 23,336 KB
最終ジャッジ日時 2025-10-02 01:39:19
合計ジャッジ時間 9,962 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using mint = modint998244353;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vmi = vector<mint>;
using vvmi = vector<vmi>;
using vvvmi = vector<vvmi>;
#define all(a) (a).begin(), (a).end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)

struct S{
    mint value;
    mint size;
};
using F = mint;

S op(S a, S b){ return {a.value+b.value, a.size+b.size}; }
S e(){ return {mint(0), 0}; }
S mapping(F f, S x){ return {x.value + f*x.size, x.size}; }
F composition(F f, F g){ return f+g; }
F id(){ return mint(0); }


int main(){
    int h, w, a, b; cin >> h >> w >> a >> b;
    vector<S> vh(h, {mint(0), mint(1)}), vw(w, {mint(0), mint(1)});
    lazy_segtree<S, op, e, F, mapping, composition, id> segh(vh);
    lazy_segtree<S, op, e, F, mapping, composition, id> segw1(vw), segw2(w);
    for(int i = 0; i+a <= h; i++){
        mint c = mint(1)/mint(h-a+1);
        segh.apply(i, i+a, c);

    }
    rep(j, w-b+1){
        mint c = mint(1)/mint(w-b+1);
        segw1.apply(j, j+b, c);
    }
    rep(i, w)segw2.set(i, {segw1.get(i).value*segw1.get(i).value, 1});
    mint ans = mint(0);
    rep(i, h){
        mint ph = segh.get(i).value;
        ans += mint(2)*segw1.all_prod().value*ph - segw2.all_prod().value*ph*ph;
    }

    cout << ans.val() << endl;
    return 0;
}
0