Project Euler – 78 : Coin partitions

 传送门

前置知识:

  1. 一点点多项式的知识
  2. 生成函数

题意:

我们设 p(n) 的含义是将n个相同的元素分成若干个的集合的方案: 集合是相同的.

意思其实就是p(n) 表示 将n这个正整数分成若干正整数相加的方案!

Screenshot.png
此为p(5) = 7的方案数

然后我们需要找出 min_n 满足 p(min_n) ≡ 0 (mod 1e6)!

分析:

我们叫P(x) 为分割函数

但是其实这道题刚开始看的时候, 感觉就是一道dp暴枚的题目, 但是事实上并没有这么简单(自己感觉每一次这类题目变一下都不好做哦)

于是我们还有一招 : 生成函数!

我们其实发现 p(n) 既然就是 分成若干的正整数的和, 那么我们容易得到它的母函数:

Screenshot.png
答案就是xn次项的系数

稍微解释一下, 就是第x个式子表示我们枚举 正整数x 的个数, 有 0, 1, 2… 这么多, 由于它们是相同元素, 所以每项的系数1, 而且对答案的贡献就是 指数 i * x, 即可取i 个 x 对答案的影响!

那么拆开的公式就是:

Screenshot.png

这里有大数学家欧拉的一个公式:

Screenshot
五边形数定理

我们可以发现它其实就是 分割函数的倒数, 即:

Screenshot.png

其中 p(k) k 的分割函数,即把 k 写成若干个正整数的和的方案数.

配合五边形数定理,我们有:

Screenshot.png

对于n(n∈Ν*) 观察等式右边会发现 x的高次系数为 0, 然后我们对于左边寻找x的n次的系数,会发现

Screenshot.png
且有一些的k是无解的

这样一来,我们就有了:

Screenshot.png

这就是递推式了, 而且大概的复杂度是捕获(看了文章之后大家口糊一下就知道了!)

定理证明:

我们首先知道:

Screenshot.png

其几何意义表示将n分成若干不同的正整数的方案!

Screenshot.png

的x的n次的系数表示的几何意义就是 n分成偶数个不同的正整数方案数 – n 分成奇数个不同的正整数的方案.

Prove:

        因为我们可以考虑就是在线性组合相乘的时候偶数个数的 -1 次会变成1对吧, 而且-1的奇数次会变成-1,所以就是有了上面的式子!

而且之所以说是不同的的正整数是因为它们的系数只有一个 x^n !

比如x^5 的系数是 1, 是因为偶数拆分有(2,3),(1,4) 奇数拆分有(5) — 所以总共有  2-1 = 1(种)

然后在引进来一个Ferrers图:

b64543a98226cffc497122e1b8014a90f603ea0e.jpg
即 24 = 12 + 5 + 4 + 3

那么我们比如让 20 = 7 +6 + 4 + 3

即:

.              0 0 0 0 0 0 0

.             0 0 0 0 0 0

.             0 0 0 0

.             0 0 0

且声明一些变量:

  1. 令 m等于Ferrers图最后一行(即最小的数对应的那一行)的元素个数,在上例中,m=3
  2. 令 s 等于Ferrers图最右边的 45度斜线 上的元素个数,这里 s=2

即:

 .             0 0 0 0 0 0 0

.             0 0 0 0 0 0

.             0 0 0 0

.             0 0 0

红色是 s , 蓝色是 m

考虑s与m的大小关系

1.s < m:

那么我们就直接将s的格子取出,另加入一行(证明显然)

 .          0 0 0 0 0 0

.          0 0 0 0 0

.          0 0 0 0

.          0 0 0

.          0 0

2.s >= m

那么我们就直接将m的格子取出,另加入前m行的末尾(证明显然) 图略…

不难发现,这样的过程能够由一种 拆分得到一对奇偶性不同的拆分,并且对一种拆分进行两次上述过程能得到原来的拆分(即操作可逆)。这使得我们可以把一种奇拆分和偶拆分对应起来,它们对 x ^ n 的 系数 +1 和 1 的贡献相互抵消,最终使得系数为 0.

这个规律对每一项都适用——除了有些时候,不是所有 nn 的拆分都能进行上述过程,有两种情形

<1>.m=s 并且45度斜线和最后一行相遇:

.             0 0 0 0 0
.             0 0 0 0
.             0 0 0

 

尝试进行上述操作,我们会得到:

.           0 0 0 0 0 0
.           0 0 0 0 0
.           0

注意到这次操作没有改变拆分的奇偶性,并且它是不可逆的

所以同时我们也可以推出这种n是什么, 即:

Screenshot.png
PS: k = m

 

<2>. m=s+1 并且45度斜线和最后一行相遇:

.             0 0 0 0 0 0
.             0 0 0 0 0
.             0 0 0 0

 

尝试进行上述操作,我们得到:
.             0 0 0 0 0
.             0 0 0 0
.             0 0 0
.             0 0 0

这显然是不合法的分割……

还是可以推出:

Screenshot.png
k = 1 – m

贡献符号均为(-1)^k

         总之,我们展示了对于一般的 n拆分成奇数个不同的正整数的方案和 n 拆分成偶数个不同的正整数的方案恰好能互相抵消

        特别地,n 若是一个广义五边形数 Screenshot.png,这种情况下 n 的奇偶拆分互相抵消之后,会留下一项,符号为 (1)^k,这恰好等于等式右边,证明完毕。

代码:

代码 (Ubuntu连接)

Anyway, hope that you can enjoy it! 🙂

4 Replies to “Project Euler – 78 : Coin partitions”

发表评论

电子邮件地址不会被公开。 必填项已用*标注