差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:namespace:整数分拆问题 [2020/05/06 15:33]
great_designer
+++ 2020-2021:teams:namespace:整数分拆问题 [2020/05/17 22:12] (当前版本)
great_designer [分拆数]
@@ 行 2: / 行 2: @@
 以下内容参考自北大版《组合数学》。
-== k部分拆数 ==
+===== k部分拆数 =====
 分拆：将自然数n写成递降正整数和的表示。
@@ 行 14: / 行 14: @@
 自0开始的分拆数：
+| n || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 |
-|-
+| p_n || 1 || 1 || 2 || 3 || 5 || 7 || 11 || 15 || 22 |
-| n || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8
-|-
-| p_n || 1 || 1 || 2 || 3 || 5 || 7 || 11 || 15 || 22
 其中恰有k个部分的分拆，称为k部分拆数，记作p(n,k)。
@@ 行 36: / 行 33: @@
 $$p(n,k)=p(n-1,k-1)+p(n-k,k)$$
-根据这个可以轻易地写出程序。
+如果像组合数一样列出表格，每个格里的数，等于左上方的数，加上该格向上方数，所在列数个格子中的数。
+| 下n右k || -1 || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 |
+| -1 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 0 || 0 || 1 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 1 || 0 || 0 || 1 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 2 || 0 || 0 || 1 || 1 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 3 || 0 || 0 || 1 || 1 || 1 || 0 || 0 || 0 || 0 || 0 |
+| 4 || 0 || 0 || 1 || 2 || 1 || 1 || 0 || 0 || 0 || 0 |
+| 5 || 0 || 0 || 1 || 2 || 2 || 1 || 1 || 0 || 0 || 0 |
+| 6 || 0 || 0 || 1 || 3 || 3 || 2 || 1 || 1 || 0 || 0 |
+| 7 || 0 || 0 || 1 || 3 || 4 || 3 || 2 || 1 || 1 || 0 |
+| 8 || 0 || 0 || 1 || 4 || 5 || 5 || 3 || 2 || 1 || 1 |
+因此按列更新对于存储更有利。根据这个可以轻易地写出程序。
+<hidden k部分拆数 p(n,k)>
 <code c>
@@ 行 70: / 行 83: @@
 </code>
-== 小结论一 ==
+</hidden>
+===== 小结论一 =====
 生成函数：一种幂级数。各项的系数为数列中的对应项。
@@ 行 76: / 行 91: @@
 由等比数列求和公式，有：
-$$1/(1-x^k )=1+x^k+x^2k+x^3k+⋯$$
+$$\frac{1}{1-x^k }=1+x^k+x^2k+x^3k+⋯$$
 $$1+p_1 x+p_2 x^2+p_3 x^3+⋯=\frac{1}{1-x}  \frac{1}{1-x^2}  \frac{1}{1-x^3}…$$
@@ 行 84: / 行 99: @@
 $$∑_{n,k=0}^∞ {p(n,k) x^n y^k }=\frac{1}{1-xy}  \frac{1}{1-x^2 y}  \frac{1}{1-x^3 y}…$$
-== 小结论二 ==
+===== 小结论二 =====
 Ferrers图：将分拆的每个部分用点组成的行表示。每行点的个数为这个部分的大小。
@@ 行 92: / 行 107: @@
 例如：分拆12=5+4+2+1的Ferrers图。
-[[文件:Ferrers图.png]]
+{{ :2020-2021:teams:namespace:ferrers图.jpg?400 |}}
 将一个Ferrers图沿着对角线翻转，得到的新Ferrers图称为原图的共轭，新分拆称为原分拆的共轭。显然，共轭是对称的关系。
@@ 行 104: / 行 119: @@
 最大k分拆数与k部分拆数相同，均为p(n,k)。
-== 互异分拆数 ==
+===== 互异分拆数 =====
 互异分拆数：〖pd〗_n。自然数n的各部分互不相同的分拆方法数。（Different）
-互异偶部分拆数：〖pe〗_n。自然数n的部分数为偶数的互异分拆方法数。（Even）
+| n || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 |
+| pd_n || 1 || 1 || 1 || 2 || 2 || 3 || 4 || 5 || 6 |
-互异奇部分拆数：〖po〗_n。自然数n的部分数为奇数的互异分拆方法数。（Odd）
-因此有：
-$${pd}_n={pe}_n+{po}_n$$
 本题要求计算互异分拆数〖pd〗_n。多组输入，其中n上界为50000，对1000007取模。
@@ 行 130: / 行 140: @@
 $$pd(n,k)=pd(n-k,k-1)+pd(n-k,k)$$
-代码如下。代码中将后一位缩减了空间，仅保留相邻两项。
+同样像组合数一样列出表格，每个格里的数，等于该格前一列上数，所在列数个格子中的数，加上该格向上方数，所在列数个格子中的数。
+| 下n右k || -1 || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 |
+| -1 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 0 || 0 || 1 || 0 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 1 || 0 || 0 || 1 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 2 || 0 || 0 || 1 || 0 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 3 || 0 || 0 || 1 || 1 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 4 || 0 || 0 || 1 || 1 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 5 || 0 || 0 || 1 || 2 || 0 || 0 || 0 || 0 || 0 || 0 |
+| 6 || 0 || 0 || 1 || 2 || 1 || 0 || 0 || 0 || 0 || 0 |
+| 7 || 0 || 0 || 1 || 3 || 1 || 0 || 0 || 0 || 0 || 0 |
+| 8 || 0 || 0 || 1 || 3 || 2 || 0 || 0 || 0 || 0 || 0 |
+因此按列更新对于存储更有利。代码中将后一位缩减了空间，仅保留相邻两项。
+<hidden k部互异分拆数 pd(n,k)>
 <code c>
@@ 行 170: / 行 196: @@
 </code>
-== 小结论三 ==
+</hidden>
-奇分拆数：自然数n的各部分都是奇数的分拆方法数。
+===== 小结论三 =====
+奇分拆数：pe_n。自然数n的各部分都是奇数的分拆方法数。
 有一个显然的等式：
-$$∏_{i=1}^∞ (1+x^i ) =\frac{∏_{i=1}^∞ (1-x^2i ) }{∏_{i=1}^∞ (1-x^i ) }=∏_{i=1}^∞ \frac{1}{1-x^{2i-1} }$$
+$$∏_{i=1}^∞ (1+x^i ) =\frac{∏_{i=1}^∞ (1-x^{2i} ) }{∏_{i=1}^∞ (1-x^i ) }=∏_{i=1}^∞ \frac{1}{1-x^{2i-1} }$$
-最左边是互异分拆数的生成函数，最右边是奇分拆数的生成函数。两者对应系数相同，因此，奇分拆数和互异分拆数相同，均为〖pd〗_n。
+最左边是互异分拆数的生成函数，最右边是奇分拆数的生成函数。两者对应系数相同，因此，奇分拆数和互异分拆数相同：
-== 分拆数 ==
+$${pe}_n={pd}_n$$
+但显然k部奇分拆数和k部互异分拆数不是一个概念，这里就不列出了。
+再引入两个概念：
+互异偶部分拆数：pde_n。自然数n的部分数为偶数的互异分拆方法数。（Even）
+互异奇部分拆数：pdo_n。自然数n的部分数为奇数的互异分拆方法数。（Odd）
+因此有：
+$${pd}_n={pde}_n+{pdo}_n$$
+同样也有相应的k部概念。由于过于复杂，不再列出。
+===== 分拆数 =====
+本题要求计算分拆数p_n。多组输入，其中n上界为50000，对1000007取模。
+单独观察分拆数的生成函数的分母部分：
+$$∏_{i=1}^∞ (1-x^i ) $$
+将这部分展开，可以想到互异分拆，与互异分拆拆出的部分数奇偶性有关。
+具体地，互异偶部分拆在展开式中被正向计数，互异奇部分拆在展开式中被负向计数。因此展开式中各项系数为两方法数之差。即：
+$$∑_{i=0}^∞ ({pde}_n-{pdo}_n ) x^n =∏_{i=1}^∞ (1-x^i ) $$
+接下来说明，多数情况下，上述两方法数相等，在展开式中系数为0；仅在少数位置，两方法数相差1或-1。
+这里只能借助构造对应的办法。
+画出每个互异分拆的Ferrers图。最后一行称为这个图的底，底上点的个数记为b（Bottom）；连接最上面一行的最后一个点与图中某点的最长45度角线段，称为这个图的坡，坡上点的个数记为s（Slide）。
+{{ :2020-2021:teams:namespace:ferrers图中的底与坡.jpg?400 |}}
+要想在互异偶部分拆与互异奇部分拆之间构造对应，就要定义变换，在保证互异条件不变的前提下，使得行数改变1：
+变换A：当b小于等于s的时候，就将底移到右边，成为一个新坡。
+变换B：当b大于s的时候，就将坡移到下边，成为一个新底。
+这两个变换，对于多数时候的n，恰有一个变换可以进行，就在互异偶部分拆与互异奇部分拆之间构造了一个一一对应。已经构造了一一对应的两部分分拆个数相等，因此这时展开式中第n项系数为0。
+变换A不能进行的条件：底与坡有一个公共点，且b=s。这种情形只发生于：
+$$n=b+(b+1)+⋯+(b+b-1)=\frac{b(3b-1)}{2}$$
+这时，展开式中第n项为：
+$$∏_{i=0}^{b-1} (-x)^{b+i} =(-1)^b ∏_{i=0}^{b-1} x^{b+i} =(-1)^b x^n$$
+变换B不能进行的条件：底与坡有一个公共点，且b=s+1。这种情形只发生于：
+$$n=(s+1)+(s+2)+⋯+(s+s)=\frac{s(3s-1)}{2}$$
+这时，展开式中第n项为：
+$$∏_{i=1}^s (-x)^{s+i} =(-1)^s ∏_{i=1}^s x^{s+i} =(-1)^s x^n$$
+至此，我们就证明了：
+$$(1-x)(1-x^2 )(1-x^3 )…=⋯+x^{26}-x^{15}+x^7-x^2+1-x+x^5-x^{12}+x^{22}-…=∑_{k=-∞}^{+∞} (-1)^k x^{\frac{k(3k-1)}{2}} $$
+将这个式子整理，对比两边各项系数，就得到递推式。
+$$(1+p_1 x+p_2 x^2+p_3 x^3+⋯)(1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+x^{26}-…)=1$$
+$$p_n=p_{n-1}+p_{n-2}-p_{n-5}-p_{n-7}+⋯$$
+这个递推式有无限项，但是如果规定负数的分拆数是0（0的分拆数已经定义为1），那么就简化为了有限项。
+本题中分拆数的计算采用这个方法。附上代码：
+<code c>
+#include<stdio.h>
+long long a[100010];
+long long p[50005];
+int main()
+{
+	p[0]=1;
+	p[1]=1;
+	p[2]=2;
+	int i;
+	for(i=1;i<50005;i++)/*递推式系数1,2,5,7,12,15,22,26...i*(3*i-1)/2,i*(3*i+1)/2*/
+	{
+		a[2*i]=i*(i*3-1)/2;/*五边形数为1,5,12,22...i*(3*i-1)/2*/
+		a[2*i+1]=i*(i*3+1)/2;
+	}
+	for(i=3;i<50005;i++)/*p[n]=p[n-1]+p[n-2]-p[n-5]-p[n-7]+p[12]+p[15]-...+p[n-i*[3i-1]/2]+p[n-i*[3i+1]/2]*/
+	{
+		p[i]=0;
+		int j;
+		for(j=2;a[j]<=i;j++)/*有可能为负数,式中加1000007*/
+		{
+			if(j&2)
+			{
+				p[i]=(p[i]+p[i-a[j]]+1000007)%1000007;
+			}
+			else
+			{
+				p[i]=(p[i]-p[i-a[j]]+1000007)%1000007;
+			}
+		}
+	}
+	int n;
+	while(~scanf("%d",&n))
+	{
+		printf("%lld\n",p[n]);
+	}
+}
+</code>

CVBB ACM Team

用户工具

站点工具

差别

页面工具