题目描述
長さ N の整数列 A があり、A1 = X, Ai+1 = Ai + D (1 ≤ i < N ) が成り立っています。
高橋君はこの整数列の要素をいくつか選んで取り、残り全てを青木君が取ります。2 人のどちらかが全てを取ることになっても構いません。
高橋君の取った数の和を S, 青木君の取った数の和を T としたとき、S − T として考えられる値は何通りあるでしょうか。
输入格式
入力は以下の形式で標準入力から与えられる。
N X D
输出格式
S − T として考えられる値の種類数を出力せよ。
题目大意
给一个首项为X,公差为D,项数为N的等差数列A,定义
w(S)=i∈S∑Ai−i∈S∑Ai
对于所有S⊆{1,2,...,N},求有多少种不同的w(S)
提示
制約
- −108 ≤ X, D ≤ 108
- 1 ≤ N ≤ 2 × 105
- 入力は全て整数である
Sample Explanation 1
A は (4, 6, 8) です。 (高橋君, 青木君) の取り方は、 ((), (4, 6, 8)), ((4), (6, 8)), ((6), (4, 8)), ((8), (4, 6))), ((4, 6), (8))), ((4, 8), (6))), ((6, 8), (4))), ((4, 6, 8), ()) の 8 通りあります。 S − T はそれぞれ −18, −10, −6, −2, 2, 6, 10, 18 であるので、値の種類数は 8 です。
Sample Explanation 2
A は (3, 0) であり、S − T として考えられる値は −3, 3 で、種類数は 2 です。