「BZOJ 1677」求和 - DP

给出一个 N N ,使用一些 2 2 的若干次幂的数相加来求之。问有多少种方法。

链接

BZOJ 1677

题解

背包问题,以 2i 2 ^ i 作为物品,求出装满背包的方案数即为答案。

时间复杂度 O(nlogn) O(n \log n) ,空间 O(n) O(n) ,需要滚动数组。

代码

#include <cstdio>
#include <algorithm>

const int MAXN = 1e6;
const int MAXN_LOG = 20; // Math.log2(1e6) = 19.931568569324174
const int MOD = 1e9;

int main()
{
    int n;
    scanf("%d", &n);

    /*
    // 注释里都是泪啊 qnqqqqqqqqq
    static int f[MAXN + 1][MAXN_LOG + 1];
    for (int i = 0; i <= MAXN_LOG; i++) f[0][i] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= MAXN_LOG; j++)
        {
            if (j != 0) f[i][j] = f[i][j - 1];
            if (i >= (1 << j)) (f[i][j] += f[i - (1 << j)][j]) %= MOD;
            // / *
            for (int k = 0; k <= j && (1 << k) <= i; k++)
            {
                // printf("  f(%d, %d) <-- f(%d, %d)\n", i, j, i - (1 << k), k);
                (f[i][j] += f[i - (1 << k)][k]) %= MOD;
            }
            // printf("f(%d, %d) = %d\n", i, j, f[i][j]);
            // * /
        }
    }
    */

    static int f[MAXN + 1];
    f[0] = 1;
    for (int i = 0; (1 << i) <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            if (j - (1 << i) >= 0) (f[j] += f[j - (1 << i)]) %= MOD;
        }
    }

    printf("%d\n", f[n]);
}