[PYTHON] Lösen Sie HHKB2020 D - Quadrate durch Drücken

Kommentar

Klicken Sie hier, um einen Link zum Problem zu erhalten. HHKB2020 D - Squares

Denkweise

(Das blaue Quadrat heißt $ S_A $ und das rote Quadrat heißt $ S_B $.)

Nachdem Sie entschieden haben, wie es in Richtung der y-Achse platziert werden soll, überlegen Sie, wie es in Richtung der x-Achse platziert werden soll.

Zu diesem Zeitpunkt ist die Bedingung, dass sich die beiden Quadrate nicht überlappen, dass eine der folgenden Bedingungen erfüllt ist. (1) Es gibt keine Überlappung in Richtung der y-Achse (die Richtung der x-Achse kann frei sein). (2) Wenn es eine Überlappung in der Richtung der y-Achse gibt, gibt es keine Überlappung in der Richtung der x-Achse

Mit diesen beiden Mustern können Sie alle Platzierungen auflisten, die das Thema ohne Auslassung erfüllen. (Mir ist klar, dass es einfacher war, über die zusätzlichen Ereignisse nachzudenken ...)

(1) Wenn es keine Überlappung in Richtung der y-Achse gibt

Überlegen Sie zunächst, wie viele Möglichkeiten in y-Achsenrichtung platziert werden sollen, z. B. ** keine Überlappung **. Setzen Sie einmal $ (y-Koordinate von S_A) <(y-Koordinate von S_B) $.

Setzen Sie anschließend $ d = N - A - B $. //////////////////////// Wenn die y-Koordinate von $ S_A $ $ [0, a] $ ist Die y-Koordinate von $ S_B $ ist $ [a, a + b], [a + 1, a + b + 1], ... [nb, n] $ $ n- (a + b) + 1 = d +1 $ Straße.

Wenn die y-Koordinate von $ S_A $ $ [1, a + 1] $ ist Die y-Koordinate von $ S_B $ ist $ d $ von $ [a + 1, a + b + 1], ... [n-b, n] $.

...

Wenn die y-Koordinate von $ S_A $ $ [n-a-b, n-b] $ ist Die y-Koordinate von $ S_B $ ist $ 1 $ von $ [n-b, n] $. /////////////////////////

Wenn also $ (y-Koordinate von S_A) <(y-Koordinate von S_B) $, Es gibt $ (d + 1) + d + ... + 1 = (d + 1) (d + 2) / 2 $ Möglichkeiten, sie in Richtung der y-Achse zu platzieren, damit sie sich nicht überlappen.

Gleiches gilt, wenn $ (y-Koordinate von S_A)> (y-Koordinate von S_B) $, also Es gibt insgesamt $ 2 (d + 1) (d + 2) / 2 = (d + 1) (d + 2) $ für die Platzierung in Richtung der y-Achse, damit sie sich nicht überlappen.

Wenn es keine Überlappung in Richtung der y-Achse gibt, überlappen sich $ S_A $ und $ S_B $ in keiner Weise in Richtung der x-Achse. Da $ S_A $ und $ S_B $ in x-Achsenrichtung in $ (n-a + 1) $ bzw. $ (n-b + 1) $ platziert sind. Der Weg, um (1) zu setzen, ist $ (d + 1) (d + 2) (n-a + 1) (n-b + 1) $.

(2) Wenn es eine Überlappung in Richtung der y-Achse gibt

Überlegen Sie zunächst, wie viele Möglichkeiten in y-Achsenrichtung platziert werden sollen, z. B. ** überlappend **. Ich weiß bereits, wie ich es ausdrücken soll, wenn sich $ (d + 1) (d + 2) $ überlappt Dieser Wert kann von der gesamten Platzierung in Richtung der y-Achse abgezogen werden. Das heißt, $ (n-a + 1) (n-b + 1) - (d + 1) (d + 2) $.

Da es eine Überlappung in Richtung der y-Achse gibt, müssen sie so platziert werden, dass sie sich nicht in Richtung der x-Achse überlappen. In diesem Problem sind die Bedingungen sowohl für die Richtung der x-Achse als auch für die Richtung der y-Achse gleich, also $ (Platzierung, die sich nicht in Richtung der x-Achse überlappt) = (Platzierung, die sich nicht in Richtung der y-Achse überlappt) $. Mit anderen Worten, die Art und Weise, wie sie so platziert werden, dass sie sich nicht in Richtung der x-Achse überlappen, ist $ (d + 1) (d + 2) $, indem das Ergebnis von (1) umgeleitet wird.

Wie oben zu platzieren (2) $ \ {(n-a + 1) (n-b + 1) - (d + 1) (d + 2) \} (d + 1) (d + 2) $ Das stimmt.

Fügen Sie danach die Ergebnisse von (1) und (2) hinzu und Sie sind fertig.

AC-Code

MOD = 10**9+7
for _ in range(int(input())):
    n,a,b = map(int, input().split())
    if a+b > n:
        print(0)
        continue

    d = n-a-b
    no_overlap = (d+1)*(d+2)
    a_free = n-a+1
    b_free = n-b+1

    ans = no_overlap*a_free*b_free + (a_free*b_free-no_overlap)*no_overlap
    print(ans%MOD)