0%

Problem 614


Problem 614


Special partitions 2

An integer partition of a number $n$ is a way of writing $n$ as a sum of positive integers. Partitions that differ only by the order of their summands are considered the same.

We call an integer partition special if 1) all its summands are distinct, and 2) all its even summands are also divisible by 4.
For example, the special partitions of 10 are:

10 = 1+4+5=3+7=1+9

The number 10 admits many more integer partitions (a total of 42), but only those three are special.

Let be $P(n)$ the number of special integer partitions of $n$. You are given that $P(1) = 1$, $P(2) = 0$, $P(3) = 1$, $P(6) = 1$, $P(10)=3$, $P(100) = 37076$ and $P(1000)=3699177285485660336$.

Find $\displaystyle \sum_{i=1}^{10^7}{P(i)}$. Give the result modulo $10^9+7$.


特殊分划

$n$的整数分划是指将$n$写成正整数之和。如果两个分划只在相加的顺序上不同,那么就视为相同的分划。

我们称一个整数分划为特殊分划,如果它满足 1) 所有用于相加的数都不相同,以及 2) 所有用于相加的偶数都能被4整除。
例如,10的特殊分划包括:

10 = 1+4+5=3+7=1+9

显然10有更多种可能的分划(总计42种),但是只有这三种是特殊分划。

记$P(n)$为$n$的特殊分划的数目。已知$P(1) = 1$,$P(2) = 0$,$P(3) = 1$,$P(6) = 1$,$P(10)=3$,$P(100) = 37076$以及$P(1000)=3699177285485660336$。

求$\displaystyle \sum_{i=1}^{10^7}{P(i)}$。将结果对$10^9+7$取余。