929. Odd-Run Compositions

A composition of $n$$n$ is a sequence of positive integers which sum to $n$$n$. Such a sequence can be split into runs, where a run is a maximal contiguous subsequence of equal terms.

For example, $2,2,1,1,1,3,2,2$$2,2,1,1,1,3,2,2$ is a composition of $14$$14$ consisting of four runs:

Let $F(n)$$F(n)$ be the number of compositions of $n$$n$ where every run has odd length.

For example, $F(5)=10$$F(5)=10$:

Find $F({10}^5)$$F(10^5)$. Give your answer modulo $1111124111$$1111124111$.

929. 奇长度相同段组成

若某正整数序列的所有元素之和是 $n$$n$，则称这是 $n$$n$ 的一个 组成。这个序列可以被拆分成若干含相同元素的极大连续段。

例如，$[2,2,1,1,1,3,2,2]$$[2,2,1,1,1,3,2,2]$ 是 $14$$14$ 的一个组成，它包含 $4$$4$ 个含相同元素的极大连续段。

记 $F(n)$$F(n)$ 为满足如下条件的序列数量：其是 $n$$n$ 的一个组成，且这个序列中，所有含相同元素的极大连续段的长度都是奇数。

例如，$F(5)=10$$F(5)=10$，这 $10$$10$ 个满足条件的序列如下：

求 $F({10}^5)$$F(10^5)$ 模 $1111124111$$1111124111$ 的值。

点 这个链接 回到源站。

点 这个链接 回到详细版题目目录。