Dernière fois Résolvez l'ABC-D d'hier.
#42 Problème
** Pensées ** Même après avoir lu l'explication, ce n'était pas rafraîchissant, donc je l'ai implémenté en référence à l'article de Kenchon. La chose importante en réfléchissant à ce problème est d'être conscient de l'intention d'écrire $ 10 ^ {100} $. Comme je l'ai écrit dans l'article de commentaire, la somme des nombres sélectionnés ne sera pas dupliquée lorsque différents nombres sont sélectionnés en raison de la présence de 10 $ ^ {100} $. De plus, la somme est un entier continu. De ce qui précède, il peut être considéré comme un problème de calcul de la somme de N + 1 nombres choisis parmi k parmi {0,1, ... N + 1}. Le nombre de sommes peut être écrit sous la forme (entier maximum composé de $ i-entier minimum composé de i + 1 $, $ k \ leq i \ leq N + 1 $). La somme minimale des $ i $ th est $ \ frac {i (i-1)} {2} $, et la somme du maximum nième à kth est $ \ frac {i (2N-i + 1)} { 2} $. Lorsque ceux-ci sont mis en œuvre,
n, k = map(int,input().split())
ans = 0
for i in range(k,n+2):
minmin = (i*(i-1))//2 #Le nom de la variable est terrible
maxmax = ((2*n-i+1)*i)//2
ans += maxmax - minmin + 1
print(ans%(10**9+7))
Ce concours était C: Facile, D: Un peu facile, E: Quoi? Alors j'ai pensé que je devais résoudre D. A bientôt, bonne nuit
Recommended Posts