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

POJ 2229 Sumsets（递推，找规律）

阅读量：5790 次

发布时间：2019-06-18

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

构造，递推，因为划分是合并的逆过程，考虑怎么合并。

先把N展开成全部为N个1

然后合并，因为和顺序无关，所以只和出现次数有关

情况有点多并且为了避免重复，分类，C[i]表示序列中最大的数为2^i时的方案数

树形表示合并（UVA 10562 Undraw the Trees的表示方法。。。

7 (2^0) (7表示2^0出现的次数)

_ _ _

| | |

1 2 3 (2^1) (7个1可以合并成1~3个2)

_ _

| |

1 1 (2^2) (继续合并)

这棵树是分形的，子树的形态由根结点的值决定。

f[n]表示方案

当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
             #include
              
               #include
               
                using namespace std;const int mod = 1e9, maxn = 1e6+1;int dp[maxn];//#define LOCALint 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] + (i&1?0:dp[i>>1]); if(dp[i]>=mod) dp[i] -= mod; } cout<
                
                 <