Day 15.
This problem requires the way of thinking.
1st, we should fix how long distance we keep.
2nd, we should fix how many balls we put in the array.
As for 2nd point, we can deny the unrealistic case by if sentence and some checking procesure.
What is important is Fixing and Checking.
Code is below.
N = int(input())
MOD = 10**9+7
#print(pow(2, N, 11))
#5
Factor = [1] * (N+1)
Inverse = [1] * (N+1)
for i in range(N):
Factor[i+1] = Factor[i]*(i+1) %MOD
Inverse[i+1] = pow(Factor[i+1],MOD-2,MOD)
def Combination(n,r):
return Factor[n]*Inverse[r]*Inverse[n-r] %MOD
for k in range(1,N+1):
answer = 0
for a in range(1,N+1):
if a + (a-1)*(k-1) > N:
break
answer += Combination(N-(a-1)*(k-1), a)
print(answer%MOD)
- harmonic series diverges.
- more detail is here.
Bye bye!