题意：转化后为给定一个数L，问L拆成N个不同的数相加的方案数，其中N>=2。

解法：其实和上次做的分解的2的幂的数量相同，由于要求每个数都不相同，这里有一个非常好的观察角度，那就是观察一个数的分解中是否存在1，再加上考虑其能够被分解的数的个数即可建立递推关系。

设f[i][j]表示数 i 被分成 j 个不同的数相加的方案数，那么考虑最后分解中不含有1，那么这部分由f[i-j][j]得到，因为后者的每一个分解出来的数都加上1就行了；接着考虑分解中含有1，那么可以假定这个1就是最后分出来的，因为分解的顺序并不影响最后的结果，由于分解中数均不相同，扣除1后，就变成了f[i-1][j-1]中不含有1的情况了，而这个结果就又可以转化为：f[i-1-(j-1)][j-1]了。整个过程非常的巧妙。一个数最多分解成多少个数相加呢？这里可以假设L被连续的1+2+...+N组成，能够推算出一个上界出来。即求一个最大的x满足x*(x+1)/2 <= L。

直接开设状态会导致TLE，由于之多只和前300来层有关系，因此来个350的第一维来滚动吧。看到另外一种压缩方法是把第二维变成01，看来两者结合起来可以使得使用内存更加小。

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;int f[350][350]; // 50000的长度也最多拆成满足等式 x*(x+1)/2<=50000 的最大的x段 // 这题和上次的一道拆分成2的幂的题目非常的像了，从一个拆分中是否有1这个元素进行递推 int ans[50005];const int MOD = 1000000;int get(int x) { int k = (int)sqrt(2.0*x); while ((k+1)*(k+2)/2 <= x) k++; while (k*(k+1)/2 > x) k--; // 准确的计算出最多由多少个元素组成 return k;}void pre() { for (int cur = 0, i = 3; i <= 50000; ++i, cur = (cur+1) % 350) { int k = get(i); f[cur][2] = (i - 1) >> 1; ans[i] = f[cur][2]; for (int j = 3; j <= k; ++j) { // 至少由两部分组成 int nxt = (cur - j + 350) % 350; f[cur][j] = (f[nxt][j] + f[nxt][j-1]) % MOD; // 这个式子的含义是从不含1和含1两个状态合并并等价而来 ans[i] = (ans[i] + f[cur][j]) % MOD; } }}int main() { int T, N; pre(); scanf("%d", &T); while (T--) { scanf("%d", &N); printf("%d\n", ans[N]); } return 0;}
          
         
        
       
      
     

 

附（未取模）：

i = 2, ret = 0

i = 3, ret = 1

i = 4, ret = 1

i = 5, ret = 2

i = 6, ret = 3

i = 7, ret = 4

i = 8, ret = 5

i = 9, ret = 7

i = 10, ret = 9

i = 11, ret = 11

i = 12, ret = 14

i = 13, ret = 17

i = 14, ret = 21

i = 15, ret = 26

i = 16, ret = 31

i = 17, ret = 37

i = 18, ret = 45

i = 19, ret = 53

i = 20, ret = 63

i = 21, ret = 75

i = 22, ret = 88

i = 23, ret = 103

i = 24, ret = 121

i = 25, ret = 141

i = 26, ret = 164

i = 27, ret = 191

i = 28, ret = 221

i = 29, ret = 255

i = 30, ret = 295

i = 31, ret = 339

i = 32, ret = 389

i = 33, ret = 447

i = 34, ret = 511

i = 35, ret = 584

i = 36, ret = 667

i = 37, ret = 759

i = 38, ret = 863

i = 39, ret = 981

i = 40, ret = 1112

i = 41, ret = 1259

i = 42, ret = 1425

i = 43, ret = 1609

i = 44, ret = 1815

i = 45, ret = 2047

i = 46, ret = 2303

i = 47, ret = 2589

i = 48, ret = 2909

i = 49, ret = 3263

i = 50, ret = 3657

i = 51, ret = 4096

i = 52, ret = 4581

i = 53, ret = 5119

i = 54, ret = 5717

i = 55, ret = 6377

i = 56, ret = 7107

i = 57, ret = 7916

i = 58, ret = 8807

i = 59, ret = 9791

i = 60, ret = 10879

i = 61, ret = 12075

i = 62, ret = 13393

i = 63, ret = 14847

i = 64, ret = 16443

i = 65, ret = 18199

i = 66, ret = 20131

i = 67, ret = 22249

i = 68, ret = 24575

i = 69, ret = 27129

i = 70, ret = 29926

i = 71, ret = 32991

i = 72, ret = 36351

i = 73, ret = 40025

i = 74, ret = 44045

i = 75, ret = 48445

i = 76, ret = 53249

i = 77, ret = 58498

i = 78, ret = 64233

i = 79, ret = 70487

i = 80, ret = 77311

i = 81, ret = 84755

i = 82, ret = 92863

i = 83, ret = 101697

i = 84, ret = 111321

i = 85, ret = 121791

i = 86, ret = 133183

i = 87, ret = 145577

i = 88, ret = 159045

i = 89, ret = 173681

i = 90, ret = 189585

i = 91, ret = 206847

i = 92, ret = 225584

i = 93, ret = 245919

i = 94, ret = 267967

i = 95, ret = 291873

i = 96, ret = 317787

i = 97, ret = 345855

i = 98, ret = 376255

i = 99, ret = 409173

i = 100, ret = 444792

i = 101, ret = 483329

i = 102, ret = 525015

i = 103, ret = 570077

i = 104, ret = 618783

i = 105, ret = 671417

i = 106, ret = 728259

i = 107, ret = 789639

i = 108, ret = 855905

i = 109, ret = 927405

i = 110, ret = 1004543

i = 111, ret = 1087743

i = 112, ret = 1177437

i = 113, ret = 1274117

i = 114, ret = 1378303

i = 115, ret = 1490527

i = 116, ret = 1611387

i = 117, ret = 1741520

i = 118, ret = 1881577

i = 119, ret = 2032289

i = 120, ret = 2194431

i = 121, ret = 2368799

i = 122, ret = 2556283

i = 123, ret = 2757825

i = 124, ret = 2974399

i = 125, ret = 3207085

i = 126, ret = 3457026

i = 127, ret = 3725409

i = 128, ret = 4013543

i = 129, ret = 4322815

i = 130, ret = 4654669

i = 131, ret = 5010687

i = 132, ret = 5392549

i = 133, ret = 5802007

i = 134, ret = 6240973

i = 135, ret = 6711479

i = 136, ret = 7215643

i = 137, ret = 7755775

i = 138, ret = 8334325

i = 139, ret = 8953855

i = 140, ret = 9617149

i = 141, ret = 10327155