Letztes Mal Löse das gestrige ABC-D.
#42 Problem
** Gedanken ** Selbst nachdem ich die Erklärung gelesen hatte, war sie nicht erfrischend, daher habe ich sie unter Bezugnahme auf Kenchons Artikel implementiert. Das Wichtigste beim Nachdenken über dieses Problem ist, sich der Absicht bewusst zu sein, dass $ 10 ^ {100} $ geschrieben wird. Wie ich im Kommentarartikel geschrieben habe, wird die Summe der ausgewählten Zahlen nicht dupliziert, wenn aufgrund des Vorhandenseins von $ 10 ^ {100} $ unterschiedliche Zahlen ausgewählt werden. Die Summe ist auch eine stetige ganze Zahl. Aus dem Obigen kann es als ein Problem der Berechnung der Summe von N + 1 Zahlen angesehen werden, die aus k aus {0,1, ... N + 1} ausgewählt wurden. Die Anzahl der Summen kann geschrieben werden als (maximale Ganzzahl aus $ i - minimale Ganzzahl aus i + 1 $, $ k \ leq i \ leq N + 1 $). Die minimale Summe des $ i $ th ist $ \ frac {i (i-1)} {2} $, und die Summe des maximalen n-ten bis k-ten ist $ \ frac {i (2N-i + 1)} { 2} $. Wenn diese implementiert sind,
n, k = map(int,input().split())
ans = 0
for i in range(k,n+2):
minmin = (i*(i-1))//2 #Der Variablenname ist schrecklich
maxmax = ((2*n-i+1)*i)//2
ans += maxmax - minmin + 1
print(ans%(10**9+7))
Dieser Wettbewerb war C: Einfach, D: Ein bisschen einfach, E: Was? Also dachte ich, ich müsste über D lösen. Wir sehen uns wieder, gute Nacht
Recommended Posts