Cliquez ici pour un lien vers le problème. HHKB2020 D - Squares
(Le carré bleu s'appelle $ S_A $ et le carré rouge s'appelle $ S_B $.)
Après avoir décidé comment le placer dans la direction de l'axe y, considérez comment le placer dans la direction de l'axe x.
À ce stade, la condition que les deux carrés ne se chevauchent pas est que l'une des conditions suivantes soit satisfaite. (1) Il n'y a pas de chevauchement dans la direction de l'axe y (la direction de l'axe x peut être libre) (2) Lorsqu'il y a chevauchement dans la direction de l'axe y, il n'y a pas de chevauchement dans la direction de l'axe x
Avec ces deux modèles, vous pouvez énumérer tous les emplacements qui satisfont le thème sans omission. (Je me rends compte qu'il était plus facile de penser aux événements supplémentaires ...)
Tout d'abord, considérez combien de façons de les placer dans la direction de l'axe des y afin qu'ils ne se chevauchent pas **. Une fois, définissez $ (coordonnée y de S_A) <(coordonnée y de S_B) $.
Ensuite, définissez $ d = N --A --B $. //////////////////////// Lorsque la coordonnée y de $ S_A $ est $ [0, a] $ La coordonnée y de $ S_B $ est $ [a, a + b], [a + 1, a + b + 1], ... [nb, n] $ $ n- (a + b) + 1 = d +1 $ rue.
Lorsque la coordonnée y de $ S_A $ est $ [1, a + 1] $ La coordonnée y de $ S_B $ est $ d $ de $ [a + 1, a + b + 1], ... [n-b, n] $.
...
Lorsque la coordonnée y de $ S_A $ est $ [n-a-b, n-b] $ La coordonnée y de $ S_B $ est $ 1 $ de $ [n-b, n] $. /////////////////////////
Par conséquent, lorsque $ (coordonnée y de S_A) <(coordonnée y de S_B) $, Il existe $ (d + 1) + d + ... + 1 = (d + 1) (d + 2) / 2 $ façons de les placer dans la direction de l'axe des y afin qu'ils ne se chevauchent pas.
Il en va de même lorsque $ (coordonnée y de S_A)> (coordonnée y de S_B) $. Il y a un total de 2 $ (d + 1) (d + 2) / 2 = (d + 1) (d + 2) $ pour le placement dans la direction de l'axe y afin qu'ils ne se chevauchent pas.
Lorsqu'il n'y a pas de chevauchement dans la direction de l'axe y, $ S_A $ et $ S_B $ ne se chevauchent en aucune façon dans la direction de l'axe x. Puisque $ S_A $ et $ S_B $ sont placés dans la direction de l'axe des x dans $ (n-a + 1) $ et $ (n-b + 1) $, respectivement. La façon de mettre (1) est $ (d + 1) (d + 2) (n-a + 1) (n-b + 1) $.
Tout d'abord, considérez le nombre de façons de placer dans la direction de l'axe y, telles que ** chevauchement **. Je sais déjà comment le mettre en cas de chevauchement dans $ (d + 1) (d + 2) $, donc Cette valeur peut être soustraite du placement entier dans la direction de l'axe y. Autrement dit, $ (n-a + 1) (n-b + 1) - (d + 1) (d + 2) $.
Puisqu'il y a un chevauchement dans la direction de l'axe y, il est nécessaire de les placer de manière à ce qu'ils ne se chevauchent pas dans la direction de l'axe x. Dans ce problème, les conditions sont les mêmes pour la direction de l'axe x et la direction de l'axe y, donc $ (placement qui ne se chevauche pas dans la direction de l'axe x) = (placement qui ne se chevauche pas dans la direction de l'axe y) $. En d'autres termes, la façon de les placer de manière à ce qu'ils ne se chevauchent pas dans la direction de l'axe x est comme $ (d + 1) (d + 2) $ en détournant le résultat de (1).
De ce qui précède, comment placer (2) $ \ {(n-a + 1) (n-b + 1) - (d + 1) (d + 2) \} (d + 1) (d + 2) $ C'est vrai.
Le reste se fait en ajoutant les résultats de (1) et (2).
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)