【ABC163 D】「Sum of Large Numbers」を解く【Python3】

コンテスト一覧へ

 

「10100, 10100+1, … , 10100+N」のN+1個の数があり、この中からK個以上の数を選ぶとき、和としてあり得るものの数を求める問題です。

答えはmod(109+7)で求める必要があります。

提出
n, k = map(int, input().split())
ans = 0

for i in range(k, n+2):
    ma = (n+n-i+1)*i//2
    mi = (i-1)*i//2
    add = ma-mi+1
    ans += add

print(int(ans%(10**9+7)))

元々の数が「10100」と大きいため、選ぶ個数が異なった際に、和が同じになることは考えられません。

よって、「K以上、N+1以下」の個数をそれぞれ考えることで導き出すことができます。

選ぶ個数が幾つであっても、それぞれの和としてあり得るものの数は

「(最大値)-(最小値)+ 1」

となります。最小値から最大値までのすべての数を、和で作ることができるためです。

 

仮にa個選ぶとした際に、和の最小値は小さいものから足していき、「0+1+2+…+a-1」となります(個数分だけ「10100」がありますが、ここでは無視しています)。

この答えは「(a-1)×a/2」となります。

「0+1+2+…+9=45」は両端から足していくことで、

「9×10/2」となることがわかります。

同様に和の最大値は大きいものから足していき、

「n+(n-1)+(n-2)+…+(n-a+1)」となるため、

「(n+(n-a+1))×a/2」で求められます。

 

最初に戻り、

(最大値「(n+(n-a+1))×a/2」)-(最小値「(a-1)×a/2」)+1

をすべての個数で調べて足していきます。

【ABC163】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。