Run ID:85289
提交时间:2024-07-16 21:18:49
def count_splitting_schemes(N, M): # 初始化dp数组,所有元素为0 dp = [[0] * (N * (N + 1) // 2 + 1) for _ in range(N + 1)] # 初始状态,当序列长度为1时,只有一种拆分方案 for i in range(1, N + 1): dp[i][1] = 1 # 动态规划填表 for i in range(2, N + 1): # 对序列长度进行循环 for j in range(1, i * (i + 1) // 2 + 1): # 对序列和进行循环 # 如果当前序列和小于等于i,则可以添加当前数字i if j >= i: dp[i][j] = dp[i - 1][j] + dp[i - 1][j - i] else: dp[i][j] = dp[i - 1][j] # 计算和为N*(N+1)/2且差值为M的拆分方案数 result = 0 for i in range((N * (N + 1) // 2 - M) // 2, N * (N + 1) // 2 + 1): if dp[N][i] != 0 and dp[N][i + M] != 0: result += dp[N][i] * dp[N][i + M] return result # 读取输入 N, M = map(int, input().split()) # 输出结果 print(count_splitting_schemes(N, M))