差别

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

--- 2020-2021:teams:namespace:整数分拆问题 [2020/05/06 16:27]
great_designer
+++ 2020-2021:teams:namespace:整数分拆问题 [2020/05/17 22:12] (当前版本)
great_designer [分拆数]
@@ 行 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>
@@ 行 69: / 行 82: @@
 </code>
+</hidden>
 ===== 小结论一 =====
@@ 行 108: / 行 123: @@
 互异分拆数：〖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>
@@ 行 169: / 行 195: @@
 </code>
+</hidden>
 ===== 小结论三 =====
-奇分拆数：自然数n的各部分都是奇数的分拆方法数。
+奇分拆数：pe_n。自然数n的各部分都是奇数的分拆方法数。
 有一个显然的等式：
@@ 行 178: / 行 206: @@
 $$∏_{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部概念。由于过于复杂，不再列出。
 ===== 分拆数 =====
@@ 行 192: / 行 236: @@
 具体地，互异偶部分拆在展开式中被正向计数，互异奇部分拆在展开式中被负向计数。因此展开式中各项系数为两方法数之差。即：
-$$∑_{i=0}^∞ ({pe}_n-{po}_n ) x^n =∏_{i=1}^∞ (1-x^i ) $$
+$$∑_{i=0}^∞ ({pde}_n-{pdo}_n ) x^n =∏_{i=1}^∞ (1-x^i ) $$
 接下来说明，多数情况下，上述两方法数相等，在展开式中系数为0；仅在少数位置，两方法数相差1或-1。

CVBB ACM Team

用户工具

站点工具

差别

页面工具