繁繁的数字背包DP

问一个数\(n\)有多少种二进制分解方案数

\(n\le 10^5\)

如7有7=4+2+1=4+1+1+1=2+2+2+1=2+2+1+1+1=2+1+1+1+1+1=1+1+1+1+1+1+1,共6种方案

一眼完全背包，将\(2^0,2^1\cdots\)等看成\(log_n\)个物品，每个物品无限件，背包体积为\(n\)。然后求方案数套个计数DP即可。

其他机房大佬都是找规律找出来的……

#include <cstdio>

#define MAXN 1000010

#define MOD 1000000007

#define ll long long

using namespace std;

int n;

ll f[MAXN];

int main()

{

	//freopen("number.in","r",stdin);

	//freopen("number.out","w",stdout);

    scanf("%d", &n);

    f[0]=1;

    int tmp=0;

    for(int i=0;tmp=(1<<i),tmp<=n;++i){

        for(int j=0;j<=n;++j)

            if(j>=tmp)

                f[j]=(f[j]+f[j-tmp])%MOD;

    }

    printf("%lld", f[n]);

    return 0;

}

巴特西

繁繁的数字背包DP

繁繁的数字背包DP

最新文章

热门文章

巴特西

繁繁的数字 背包DP

繁繁的数字 背包DP

最新文章

热门文章

繁繁的数字背包DP

繁繁的数字背包DP