D - Sum of Large Numbers
Editorial
/ 
/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
10^{100}, 10^{100}+1, ..., 10^{100}+N の N+1 個の数があります。
この中から K 個以上の数を選ぶとき、その和としてあり得るものの個数を \bmod (10^9+7) で求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq N+1
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
和としてあり得るものの個数を \bmod (10^9+7) で出力せよ。
入力例 1
3 2
出力例 1
10
以下の 10 通りが考えられます。
- (10^{100})+(10^{100}+1)=2\times 10^{100}+1
- (10^{100})+(10^{100}+2)=2\times 10^{100}+2
- (10^{100})+(10^{100}+3)=(10^{100}+1)+(10^{100}+2)=2\times 10^{100}+3
- (10^{100}+1)+(10^{100}+3)=2\times 10^{100}+4
- (10^{100}+2)+(10^{100}+3)=2\times 10^{100}+5
- (10^{100})+(10^{100}+1)+(10^{100}+2)=3\times 10^{100}+3
- (10^{100})+(10^{100}+1)+(10^{100}+3)=3\times 10^{100}+4
- (10^{100})+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+5
- (10^{100}+1)+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+6
- (10^{100})+(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=4\times 10^{100}+6
入力例 2
200000 200001
出力例 2
1
全てを選ぶしかないので 1 通りです。
入力例 3
141421 35623
出力例 3
220280457
Score : 400 points
Problem Statement
We have N+1 integers: 10^{100}, 10^{100}+1, ..., 10^{100}+N.
We will choose K or more of these integers. Find the number of possible values of the sum of the chosen numbers, modulo (10^9+7).
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq K \leq N+1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K
Output
Print the number of possible values of the sum, modulo (10^9+7).
Sample Input 1
3 2
Sample Output 1
10
The sum can take 10 values, as follows:
- (10^{100})+(10^{100}+1)=2\times 10^{100}+1
- (10^{100})+(10^{100}+2)=2\times 10^{100}+2
- (10^{100})+(10^{100}+3)=(10^{100}+1)+(10^{100}+2)=2\times 10^{100}+3
- (10^{100}+1)+(10^{100}+3)=2\times 10^{100}+4
- (10^{100}+2)+(10^{100}+3)=2\times 10^{100}+5
- (10^{100})+(10^{100}+1)+(10^{100}+2)=3\times 10^{100}+3
- (10^{100})+(10^{100}+1)+(10^{100}+3)=3\times 10^{100}+4
- (10^{100})+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+5
- (10^{100}+1)+(10^{100}+2)+(10^{100}+3)=3\times 10^{100}+6
- (10^{100})+(10^{100}+1)+(10^{100}+2)+(10^{100}+3)=4\times 10^{100}+6
Sample Input 2
200000 200001
Sample Output 2
1
We must choose all of the integers, so the sum can take just 1 value.
Sample Input 3
141421 35623
Sample Output 3
220280457