分割数
code: partition
def partition(N, M, L, R, f):
"""
N を L, Rの自然数 M 個に分割する
f = Trueのとき合計がNと一致, Falseなら余りがあってもよい
条件を満たす列 T に対し何らかの check()関数を定義して用いる
"""
if L * M > N:
return
if f and R * M < N:
return
NN = N - L * M
T = L * M
def rec(i, K):
if i == M:
check(T)
return
if K == NN:
check(T)
return
if f and R * (M - i) == NN:
for j in range(i, M):
Tj = R
check(T)
for j in range(i, M):
Tj = L
return
l = 0
if f:
l = max(0, NN - K - R * (M - (i+1)))
r = max(l, min(R, NN - K))
for k in range(l, r+1):
Ti += k
rec(i+1, K+k)
Ti -= k
rec(0, 0)
def check(arr):
pass