2020-2021:teams:namespace:整数分拆问题
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:namespace:整数分拆问题 [2020/05/06 15:52] great_designer |
2020-2021:teams:namespace:整数分拆问题 [2020/05/17 22:12] (当前版本) great_designer [分拆数] |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| 以下内容参考自北大版《组合数学》。 | 以下内容参考自北大版《组合数学》。 | ||
| - | == k部分拆数 == | + | ===== k部分拆数 ===== |
| 分拆：将自然数n写成递降正整数和的表示。 | 分拆：将自然数n写成递降正整数和的表示。 | ||
| 行 14: | 行 14: | ||
| 自0开始的分拆数： | 自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)。 | 其中恰有k个部分的分拆，称为k部分拆数，记作p(n,k)。 | ||
| 行 36: | 行 33: | ||
| $$p(n,k)=p(n-1,k-1)+p(n-k,k)$$ | $$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> | <code c> | ||
| 行 70: | 行 83: | ||
| </code> | </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}…$$ | $$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}…$$ | $$∑_{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图：将分拆的每个部分用点组成的行表示。每行点的个数为这个部分的大小。 | Ferrers图：将分拆的每个部分用点组成的行表示。每行点的个数为这个部分的大小。 | ||
| 行 104: | 行 119: | ||
| 最大k分拆数与k部分拆数相同，均为p(n,k)。 | 最大k分拆数与k部分拆数相同，均为p(n,k)。 | ||
| - | == 互异分拆数 == | + | ===== 互异分拆数 ===== |
| 互异分拆数：〖pd〗_n。自然数n的各部分互不相同的分拆方法数。（Different） | 互异分拆数：〖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取模。 | 本题要求计算互异分拆数〖pd〗_n。多组输入，其中n上界为50000，对1000007取模。 | ||
| 行 130: | 行 140: | ||
| $$pd(n,k)=pd(n-k,k-1)+pd(n-k,k)$$ | $$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> | <code c> | ||
| 行 170: | 行 196: | ||
| </code> | </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} }$$ | $$∏_{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取模。 | 本题要求计算分拆数p_n。多组输入，其中n上界为50000，对1000007取模。 | ||
| 行 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。 | 接下来说明，多数情况下，上述两方法数相等，在展开式中系数为0；仅在少数位置，两方法数相差1或-1。 | ||
2020-2021/teams/namespace/整数分拆问题.1588751570.txt.gz · 最后更改: 2020/05/06 15:52 由 great_designer
