3382. 整数拆分
摘要
Title: 3382. 整数拆分
Tag: 完全背包
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3382. 整数拆分
-
题意
一个整数总可以拆分为 2的幂的和
用 f(n)表示 n的不同拆分的种数，例如 f(7)=6
要求编写程序，读入 n，输出 f(n)mod109 -
思路
完全背包问题 求方案数
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26'''
Author: NEFU AB-IN
Date: 2023-03-23 16:16:15
FilePath: \Acwing\3382\3382.py
LastEditTime: 2023-03-23 19:43:52
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations
N = int(1e6 + 10)
INF = int(2e9)
MOD = int(1e9)
dp = [0] * N
n = int(input())
dp[0] = 1
i = 1
while i <= n:
for j in range(i, n + 1):
dp[j] = (dp[j] + dp[j - i]) % MOD
i *= 2
print(dp[n])
