---

Problem 588

---

Quintinomial coefficients

The coefficients in the expansion of $(x+1{)}^k$ are called binomial coefficients.
Analoguously the coefficients in the expansion of $(x^4+x^3+x^2+x+1{)}^k$ are called quintinomial coefficients.
(quintus= Latin for fifth).

Consider the expansion of $(x^4+x^3+x^2+x+1{)}^3$:
$x^{12}+3x^{11}+6x^{10}+10x^9+15x^8+18x^7+19x^6+18x^5+15x^4+10x^3+6x^2+3x+1$
As we can see 7 out of the 13 quintinomial coefficients for $k=3$ are odd.

Let $Q(k)$ be the number of odd coefficients in the expansion of $(x^4+x^3+x^2+x+1{)}^k$.
So $Q(3)=7$.

You are given $Q(10)=17$ and $Q(100)=35$.

Find $\sum _{k=1}^{18}Q({10}^k)$.

---

五项式系数

$(x+1{)}^k$展开的各项系数被称为二项式系数。
类似地，$(x^4+x^3+x^2+x+1{)}^k$展开的各项系数被称为五项式系数。
（quintus是表示“第5”的拉丁语词汇）。

考虑$(x^4+x^3+x^2+x+1{)}^3$的展开式：
$x^{12}+3x^{11}+6x^{10}+10x^9+15x^8+18x^7+19x^6+18x^5+15x^4+10x^3+6x^2+3x+1$
我们可以看出，当$k=3$时，13个五项式系数中有7个是奇数。

令$Q(k)$表示$(x^4+x^3+x^2+x+1{)}^k$的展开式的系数中奇数的数目。
因此$Q(3)=7$。

已知$Q(10)=17$以及$Q(100)=35$。

求$\sum _{k=1}^{18}Q({10}^k)$。

---