HHKB プログラミングコンテスト 2020 D - Squares

D - Squares

問題へのリンク

解説

• X(答え)

重ならないという現象の数え上げは難しいので、重なる(X1)を数えて全体から引く X = X0 - X1 X0 = (N-A+1)² * (N-B+1)²

• X1(重なる)

重なるという現象は、AとBの満たす区間がxでもyでも重なるときで対称性から、 xで重なるときの場合の数をX2とすれば、 X1 = X2² である

• X2(一次元の重なり)

これは、重ならない(X3)の方が扱いやすいので、全体(X2_0)から引くことにする X2 = X2_0 - X3 X2_0 = (N-A+1) * (N-B+1) - X3(一次元で重ならない)

Aが左にあるか右にあるかで場合わけした場合、それらの場合の数は全く同じになるので Aが左で固定して考え、後で2倍する Aが左のとき、Aの場所が決定すれば、Bの場合の数は決まる。 1 + 2 + ... + N-A-B+1 が答えである。 これは、(N-A-B+1) * (N-A-B+2) / 2なので、X3はこの2倍で X3 = (N-A-B+1) * (N-A-B+2)

実装

void solve(){
    ll N, A, B;
    cin >> N >> A >> B;
    if(N < A + B){
        cout << 0 << endl;
        return;
    }
    mint X3 = mint(N-A-B+1) * mint(N-A-B+2);
    mint X2_0 = mint(N-A+1) * mint(N-B+1);
    mint X2 = X2_0 - X3;
    mint X1 = X2 * X2;
    mint X0 = mint(N-A+1) * mint(N-A+1) * mint(N-B+1) * mint(N-B+1);
    mint X = X0 - X1;
    cout << X << endl;
}