魔法深渊

题目难度：二星
考察点：动态规划、预处理

方法1：暴力、动态规划

1. 分析：

算法实现：
(1). 用一个数组p表示2的幂，其中p[i]=2^i
(2). 输入n，然后从1遍历到n，在来一个内层循环j表示2^j，然后如果i >= p[j]， dp[i] += dp[i-p[j]]，不要忘记取模
(2). 输出结果dp[n]。

2. 复杂度分析：

3. 代码：

#include 
using namespace std;
typedef long long LL;
int p[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
const int MAXN = 1e3+5;
const int MOD = 1e9+3;
LL dp[MAXN];
int main() {
 int m; cin>>m;
 while(m--) {
     int n; cin>>n;
     memset(dp, 0, sizeof dp);
     dp[0] = 1;
     for(int i=1; i<=n; i++) {
         for(int j=0; j<10; j++) {
             if(i < p[j]) break;
             dp[i] = (dp[i] + dp[i-p[j]]) % MOD;
         }
     }
     cout<<dp[n]<<endl;
 }
 return 0;
}

方法2：预处理、动态规划

1. 
   

   分析：

   其实在上述的代码中，我们其实没有必要在m层循环中，每次都计算一遍dp[n]，这样是浪费时间的，我们可以提前预处理一下dp[n]的计算方法，这样在循环中只需要输入一个n，输出一个dp[n]即可，具体详见代码。

2. 
   

   复杂度分析：

   时间复杂度：O(max(nlog(n), m))
   空间复杂度：O(n)

3. 代码：

   #include 
   using namespace std;
   typedef long long LL;
   int p[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512};
   const int MAXN = 1e3+5;
   const int MOD = 1e9+3;
   LL dp[MAXN];
   void Init() {
    dp[0] = 1;
    for(int i=1; i<MAXN; i++) {
        for(int j=0; j<10; j++) {
            if(i < p[j]) break;
            dp[i] = (dp[i] + dp[i-p[j]]) % MOD;
        }
    }
   }
   int main() {
    int m; cin>>m;
    Init();
    while(m--) {
        int n; cin>>n;
        cout<<dp[n]<<endl;
    }
    return 0;
   }