37 lines
No EOL
1.1 KiB
Python
37 lines
No EOL
1.1 KiB
Python
import sys
|
|
|
|
data = sys.stdin.read().split()
|
|
if data:
|
|
target_N = int(data[0])
|
|
target_H = int(data[1])
|
|
MOD = 786433
|
|
if target_H > 30:
|
|
print(0)
|
|
sys.exit(0)
|
|
min_n = [0] * 35
|
|
min_n[0] = 0
|
|
min_n[1] = 1
|
|
for h in range(2, 35):
|
|
min_n[h] = min_n[h-1] + min_n[h-2] + 1
|
|
dp = [[0] * (target_N + 1) for _ in range(target_H + 2)]
|
|
dp[0][0] = 1
|
|
if target_N >= 1:
|
|
dp[1][1] = 1
|
|
for h_idx in range(2, target_H + 2):
|
|
h_real = h_idx - 1
|
|
if min_n[h_real + 1] > target_N:
|
|
break
|
|
for n in range(min_n[h_real + 1], target_N + 1):
|
|
ways = 0
|
|
min_k = min_n[h_idx - 2]
|
|
max_k = n - 1 - min_n[h_idx - 2]
|
|
if min_k > max_k:
|
|
continue
|
|
for k in range(min_k, max_k + 1):
|
|
r = n - 1 - k
|
|
w1 = dp[h_idx-1][k] * dp[h_idx-1][r]
|
|
w2 = dp[h_idx-1][k] * dp[h_idx-2][r]
|
|
w3 = dp[h_idx-2][k] * dp[h_idx-1][r]
|
|
ways += w1 + w2 + w3
|
|
dp[h_idx][n] = ways % MOD
|
|
print(dp[target_H + 1][target_N]) |