1 / 1

319 : 有界数列

$x_1, x_2, \dots, x_n$ を以下のような長さ $n$ の数列とする.

$x_1 = 2$
$1 < i \leq n$ について $x_{i-1} < x_i$
$1 \leq i,j \leq n$ について $(x_i)^j < (x_j+1)^i$

長さ2のこのような数列は $\{2,4\}, \{2,5\}, \{2,6\}, \{2,7\}, \{2,8\}$ の5つのみである. 長さ5のこのような数列は293ある. 以下がそのうちの3つの例である. $\{2,5,11,25,55\}, \{2,6,14,36,88\}, \{2,8,22,64,181\}$

$t(n)$ を長さ $n$ のこのような数列の個数とする. $t(10) = 86195, t(20) = 5227991891$ である.

$t(10^{10})$ を $\mod 10^9$ で求めよ.

319 : 有界数列

$x_1, x_2, \dots, x_n$ を以下のような長さ $n$ の数列とする.

$x_1 = 2$
$1 < i \leq n$ について $x_{i-1} < x_i$
$1 \leq i,j \leq n$ について $(x_i)^j < (x_j+1)^i$

$t(n)$ を長さ $n$ のこのような数列の個数とする. $t(10) = 86195, t(20) = 5227991891$ である.

$t(10^{10})$ を $\mod 10^9$ で求めよ.