Competitive Programing Typical 90 Problem day15

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))
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:
    answer += Combination(N-(a-1)*(k-1), a)
  • harmonic series diverges.

Bye bye!