Sumsets
Farmer John commanded his cows to search for different sets of numbers that sum to a given number. The cows use only numbers that are an integer power of 2. Here are the possible sets of numbers that sum to 7:
1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4
Help FJ count all possible representations for a given integer N (1 <= N <= 1,000,000).
Input
A single line with a single integer, N.
Output
The number of ways to represent N as the indicated sum. Due to the potential huge size of this number, print only last 9 digits (in base 10 representation).
Sample Input
7
Sample Output
6
Source
题目类型：完全背包
算法分析：dp[i]表示第i个数所能够拆分的方案数，可以将每个2的幂值看作是一个物品花费。则状态转移方程为dp[j] = (dp[j] + dp[j-i]) % 1e9，其中1 <= i <= pow (2, floor (log2 (n)))，初始条件dp[0] = 1，最后直接输出dp[n]即可
|
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 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
/************************************************* Author :supermaker Created Time :2015/11/23 18:10:10 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e6 + 6666; int dp[maxn]; int main() { //CFF; //CPPFF; int n, mod = 1e9; while (scanf ("%d", &n) != EOF) { int val = (int) (log10 (n) / log10 (2)); memset (dp, 0, sizeof (dp)); dp[0] = 1; int tt = (1 << val); for (int i = 1; i <= tt; i *= 2) { for (int j = i; j <= n; j++) dp[j] = (dp[j] + dp[j-i]) % mod; } printf ("%d\n", dp[n]); } return 0; } |
- « 上一篇：hdu1284
- hdu1203：下一篇 »