HPU1480: 又是划分问题

深藏阁楼爱情的钟 2022-05-18 04:35 184阅读 0赞

1480: 又是划分问题  
时间限制: 1 Sec 内存限制: 512 MB

提交: 123 解决: 34 统计  
**题目描述**  
给你一个正整数n，将其划分，要求划分成的数必须是2的幂，有多少种划分方法？？  
结果可能很大，我们输出对1e9+7取模的结果  
**输入**  
一个正整数n,代表要划分的数；  
1≤n≤107  1 ≤ n ≤ 10 7   
**输出**  
输出可划分的方法数  
**样例输入**  
15  
67  
**样例输出**  
26  
2030  
**提示**  
当n=6时，我们可以将其划分为  
1 1 1 1 1 1  
1 1 1 1 2  
1 1 2 2  
2 2 2  
1 1 4  
2 4  
这6种划分方法

--------------------

比赛的时候没做出来，今天补题的时候想着用完全背包的思想来解决，可是超时了，只能用规律来做了，

思路：  
dp。每个状态dp\[i\]可有两种状态得来，一种是dp\[i\]=dp\[i−1\]  d p \[ i \] = d p \[ i − 1 \]  , 另一种是(dp\[i−1）\+dp\[i>>1\])  ( d p \[ i − 1 ） + d p \[ i >> 1 \] ) 得来。**前者是i为奇数**时的状态转移，**后者是偶数**时。对于奇数i来说，是（i-1）增加了1，而且除以2以后和（i-1)/2相等，所以他的所有情况和（i-1）的情况相同，而对于偶数i来说，他在dp\[i-1\]的基础上增加了一种新的组合方式，即dp\[i>>1\]

## 规律 Orz ##

dp\[i\]=\{ dp\[i−1\]dp\[i−1\]\+dp\[i>>1\]i是奇数i是偶数  d p \[ i \] = \{ d p \[ i − 1 \] i 是 奇 数 d p \[ i − 1 \] + d p \[ i >> 1 \] i 是 偶 数

--------------------

就这样子

f[0]=1;
        f[1]=1;
        for(int i=2;i<MAXN;i++)
            if(i&1) f[i]=f[i-1];
            else    f[i]=f[i-1]%mod+f[i>>1]%mod;

AC代码：  
规律 Orz

/*
        利用规率， 
    */
    #include<bits/stdc++.h>
    using namespace std;
    const int mod=1e9+7;
    const int MAXN=1e7+7;
    int f[MAXN];
    
    int main() 
    {
        f[0]=1;
        f[1]=1;
        for(int i=2;i<MAXN;i++)
            if(i&1) f[i]=f[i-1];
            else    f[i]=f[i-1]%mod+f[i>>1]%mod;
    
        int n;
        while(~scanf("%d",&n)) 
            printf("%d\n",f[n]%mod);
        return 0;
    }