数学：整数拆分

使用五边形数定理进行整数拆分

先介绍一个叫做分拆数的概念：

将一个数用一个或多个正整数的无序和来表示

例如4的分拆有5种：4 , 3+1 , 2+2 , 2+1+1 , 1+1+1+1

还有一个概念叫做限制分拆，就是给分拆加上限制条件，下面给出一些常见的结论

n的分拆数中最大部分为m的个数=把n分拆成m部分的个数

n的分拆数中每一部分都小于等于m的个数=把n分成m份或更小

的分拆数中每部分的数都相等的个数=n 的因子个数
Eg. 6=2+2+2, 6=3+3,6=1+1+1+1+1+1

的分拆数中每部分都是1或2(或者把n分拆成1或2部分)的个数=floor(n/2+1);
Eg. 6=1+1+1+1+1+1, 6=1+1+1+1+2, 6=1+1+2+2, 6=2+2+2
floor()是向下取整

n的分拆数中每部分都是1或2或3(或者把n分拆成1或2或3部分)的个数=(n+3)^2/12;

然后是要点总结部分，转自https://blog.csdn.net/whai362/article/details/42530243

至于问题的变式，等介绍完母函数（生成函数）之后再进行介绍

HDU4651

 1 #include<cstdio>
 2 using namespace std;
 3 const int MOD=1e9+7;
 4 int n;
 5 int dp[100005];
 6 void init()
 7 {
 8     dp[0]=1;
 9     for(int i=1;i<=100000;i++)
10     {
11         for(int j=1,r=1;i-(3*j*j-j)/2>=0;j++,r*=-1)
12         {
13             dp[i]+=dp[i-(3*j*j-j)/2]*r;
14             dp[i]%=MOD;
15             dp[i]=(dp[i]+MOD)%MOD;
16             if(i-(3*j*j+j)/2>=0)
17             {
18                 dp[i]+=dp[i-(3*j*j+j)/2]*r;
19                 dp[i]%=MOD;
20                 dp[i]=(dp[i]+MOD)%MOD;
21             }
22         }
23     }
24 }
25 int main()
26 {
27     init();
28     int T;
29     scanf("%d",&T);
30     while(T--)
31     {
32         scanf("%d",&n);
33         printf("%d
",dp[n]);    
34     }
35     return 0;
36 }