POJ 2229 Sumsets（递推，找规律）-白红宇

POJ 2229 Sumsets（递推，找规律）

阅读量：793 次

发布时间：2023-03-03

本文共 755 字，大约阅读时间需要 2 分钟。

构造递推关系，因为划分是合并的逆过程，需要考虑如何合并。将N展开成全部由1组成的N个1，然后合并。由于合并顺序无关，只与出现次数有关，因此需要进行分类。

设C[i]表示序列中最大的数为2^i时的方案数。通过树形结构可以表示合并过程。例如，7表示2^0出现的次数。树的结构是分形的，子树的形态由根结点的值决定。

当n是偶数时，第一层会增加一颗子树，其值为n/2，递推关系为f[n] = f[n-1] + f[n/2]。当n是奇数时，树的形态不变，递推关系为f[n] = f[n-1]。

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
#include 
       
        
#include 
        
          #include 
          #include 
          
            #include 
           
             using namespace std; const int mod = 1e9, maxn = 1e6 + 1; int dp[maxn]; #define LOCAL int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); #endif int n; cin >> n; dp[1] = 1; for (int i = 2; i <= n; ++i) { dp[i] = dp[i-1]; if (i > 1) { dp[i] += dp[i / 2]; } if (dp[i] >= mod) { dp[i] -= mod; } } cout << dp[n]; }

以上代码实现了递推关系的计算，返回了最终的dp[n]值。

转载地址：http://fyxfk.baihongyu.com/

你可能感兴趣的文章