Last time Solve yesterday's ABC-D.
#42 Problem
** Thoughts ** Even after reading the explanation, it wasn't refreshing, so I implemented it with reference to Kenchon's article. The important thing in thinking about this issue is to be aware of the intent that $ 10 ^ {100} $ is written. As I wrote in the commentary article, the sum of the selected numbers will not be duplicated when different numbers are selected due to the presence of $ 10 ^ {100} $. Also, the sum is a continuous integer. From the above, it can be considered as a problem of calculating the sum of the numbers selected from k to N + 1 from {0,1, ... N + 1}. The number of sums can be written as (the largest integer that can be made from $ i-the smallest integer that can be made from i + 1 $, $ k \ leq i \ leq N + 1 $). The minimum sum of the $ i $ th is $ \ frac {i (i-1)} {2} $, and the sum of the maximum nth to kth is $ \ frac {i (2N-i + 1)} { 2} $. When these are implemented,
n, k = map(int,input().split())
ans = 0
for i in range(k,n+2):
minmin = (i*(i-1))//2 #Variable name is terrible
maxmax = ((2*n-i+1)*i)//2
ans += maxmax - minmin + 1
print(ans%(10**9+7))
This contest was C: Easy, D: A little easy, E: What? So I thought I had to solve about D. See you again, good night
Recommended Posts