抱歉，您的浏览器无法访问本站

本页面需要浏览器支持（启用）JavaScript


了解详情 >

[原创]51nod 1383&1048 整数分解为2的幂 [递推]【数学】

Tabris

CSDN数学思维51nod

发布于：2017年3月2日

次浏览

[原创]51nod 1383&1048 整数分解为 2 的幂 [递推]【数学】

2017-03-02 09:28:49 Tabris_ 阅读数：477

博客爬取于 2020-06-14 22:41:32
以下为正文

版权声明：本文为 Tabris 原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/59480949

题目连接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1048

-------------------------------------------------------------------------------------------------------------.
整数分解为 2 的幂

基准时间限制：3 秒 空间限制：131072 KB 分值： 1280 难度：9 级算法题

任何正整数都能分解成 2 的幂，给定整数 N，求 N 的此类划分方法的数量！
比如 N = 7 时，共有 6 种划分方法。

7=1+1+1+1+1+1+1
=1+1+1+1+1+2
=1+1+1+2+2
=1+2+2+2
=1+1+1+4
=1+2+4

Input
输入 N（1 <= N <= 10^30)

Output
划分方法的数量

Input 示例

7

Output 示例

6
-------------------------------------------------------------------------------------------------------------.

首先能够 dp

设 dp[i][j]表示组成的数是i，方案中最大的数是 $2^j的方案数。 为了避免重复，dp[i][j]转移时枚举下一个数必须大于等于$2^j
那么可以得出：dp[i][j]=\sum^{j}_{k=0}dp[i−2^j][k]

能够做到O(n\log(n))的复杂度

通过打表找规律等 ，可以递推得到如下规律

dp[i] = dp[i-2] + dp[i/2] ,i为偶数 \\ dp[i] = dp[i-1] ,i为奇数

这样的话复杂度就是O(n)

然而对于 51nod 1383 这个复杂度就够用了，但是对于 1048 的n(10^{30})，就完全不够用了，

如果 n 很大怎么办？
那样就要挖掘一下分解方案的性质了。

1.对于一个数 n，假设它二进制下有 m 个 1，分别是第a_1,a_2…a_m位。对于 n 的任意一种分解方案，把所有 2 的幂升序排序，然后可以划分成 m 段，其中第 i 段的和是 $2^{a_i} 2.对于一个数$2^i的一种划分方案，如果不是只有它本身一个数，一定可以把这些 2 的幂升序排序，然后分成两段，每一段的和都是 $2^{i−1}$

证明并不难。有了这些性质，就可以设新的状态了。

首先设 g[i][j]表示做完了前 i 段（即 n 二进制下的前 i 个 1 位），最大的数是 $2^j，方案数是多少。 再设一个辅助数组f[i][j]，表示组成$2^i，最大的数是 $2^j的方案数。 接下来枚举第i-1段的最大数是多少，假设是$2^k，那么g[i][j]=\sum^{j}_{k=0}g[i−1][k]∗f[i−k][j−k]
其中i-k,j-k的意义在于：要控制后面的数都大于等于 $2^k，每个数都要除掉$2^k，那么就不会算重了。
f[i][j]的转移类似

时间复杂度O(\log ^{3}(n)∗高精度)

转(chao)自(xi)

附本题代码
----------------------------------------------------------------------------------.

O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int dp[N];
int main(){
    int n;
    scanf("%d",&n);
    dp[0]=1;
    for(int i=1;i<=n;i++){
        if(i&1){
            dp[i]=dp[i-1];
        }
        else {
            dp[i]=dp[i-1]+dp[i/2];
        }
        if(dp[i]>MOD) dp[i]-=MOD;
    }
    printf("%d\n",dp[n]);
    return 0;
}

O(\log ^{3}(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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
# include <cstdio>
# include <cstring>
# include <algorithm>

using namespace std;

const int N=99,M=170,mo=1e9;

typedef long long LL;

char c[N];

int tot;

struct num
{
    int w,a[M];
}f[N+5][N+5],ans,n,p,t,s[N+5],g[N+5][N+5];

num operator + (const num &a,const num &b)
{
    t.w=max(a.w,b.w);
    //t.a[1]=0;
    memset(t.a,0,sizeof(t.a));
    for (int i=1;i<=t.w;i++)
    {
        t.a[i]+=a.a[i]+b.a[i];
        if (t.a[i]>=mo)
        {
            t.a[i+1]=1;
            t.a[i]-=mo;
        }//else t.a[i+1]=0;
    }
    if (t.a[t.w+1]>0) t.w++;
    //memset(t.a+t.w+1,0,sizeof(t.a+t.w+1));
    return t;
}

num operator * (const num &a,const num &b)
{
    memset(t.a,0,sizeof(t.a));
    for (int i=1;i<=a.w;i++)
    {
        for (int j=1;j<=b.w;j++)
        {
            t.a[i+j]+=(t.a[i+j-1]+(LL)a.a[i]*b.a[j])/mo;
            t.a[i+j-1]=(t.a[i+j-1]+(LL)a.a[i]*b.a[j])%mo;
        }
    }
    for (t.w=a.w+b.w;t.w>1 && t.a[t.w]==0;t.w--);
    return t;
}

int main()
{
    freopen("data.out","w",stdout);
    scanf("%s",c+1);
    int l=strlen(c+1);
    n.w=l/9+1;
    for (int i=1;i<=l;i++)
    {
        int j=(l-i)/9;
        n.a[j+1]=n.a[j+1]*10+c[i]-48;
    }
    f[0][0].w=f[0][0].a[1]=1;
    for (int i=1;i<=N;i++)
    {
        for (int j=0;j<i;j++)
        {
            for (int k=0;k<=j;k++)
            {
                f[i][j]=f[i][j]+f[i-1][k]*f[i-1-k][j-k];
            }
        }
        f[i][i].w=f[i][i].a[1]=1;
    }
    tot=0;
    for (int i=0;i<=N;i++)
    {
        if (n.a[1]&1)
        {
            tot++;
            if (tot==1)
            {
                for (int j=0;j<=i;j++) g[1][j]=f[i][j];
            }else
            {
                for (int j=0;j<=i;j++)
                {
                    for (int k=0;k<=j;k++)
                    {
                        g[tot][j]=g[tot][j]+g[tot-1][k]*f[i-k][j-k];
                    }
                }
            }
        }
        int r=0;
        for (int j=n.w;j;j--)
        {
            int t=n.a[j];
            n.a[j]=((LL)r*mo+t)/2;
            r=((LL)r*mo+t)%2;
        }
    }
    for (int i=0;i<=N;i++) ans=ans+g[tot][i];
    printf("%d",ans.a[ans.w]);
    for (int i=ans.w-1;i;i--)
    {
        for (int j=1e8;j;j/=10)
        {
            printf("%d",ans.a[i]/j);
            ans.a[i]%=j;
        }
    }
    printf("\n");
    return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://blog.tabris.top/acm/2017-03-02-59480949/

本页文档最后更新于：2021年5月16日

CSDN

评论