No.821 Making Integers
Pulmn
ixmelProblem Statement
You are given positive integers $N,K$. Find the number of distinct possible values of the sum of the sequence $A$ after performing the following operation between $0$ and $K$ times, inclusive, on the sequence $A=(1,2,\dots ,N)$ of length $N$.
Operation: Choose an integer $i$ satisfying $1\le i\le N$, and multiply the value of $A_i$ by $-1$.
Input
$N$ $K$
$1\le K\le N\le 10^9$
Output
Print the number of distinct possible values of the sum of the sequence $A$ after the operations. Print a newline at the end.
Sample
Sample 1
Input
3 2
Output
6
The possible sequences $A$ after the operations are $(1,2,3),(-1,2,3),(1,-2,3),(1,2,-3),(-1,-2,3),(-1,2,-3),(1,-2,-3)$. Their sums are $6,4,2,0,0,-2,-4$, respectively, so there are $6$ possible values for the sum of the sequence after the operations.
Sample 2
Input
987654321 123456789
Output
114311841799268404
The answer may not fit in a 32-bit integer type.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。