33OJ
登录 注册

#P17571. 「FAOI-R(-2)」数列计数 2024

    ID: 20098 远端评测题 1000ms 32MiB 尝试: 0 已通过: 0 显示难度NOI/NOI+/CTS 上传者: 标签>递推倍增2024矩阵加速

「FAOI-R(-2)」数列计数 2024

背景

本题为「FAOI-R2」A trip to Macao 的加强版,曾被放入 OIFC 2024 NOIP 联考。

题目描述

给定正整数 nn。对于一个长度为 kk 的正整数数列 {a}\{a\},称它是好的当且仅当:

  • a1=1a_1 = 1,ak=na_k=n。
  • 对于所有 2≤i≤k2\le i\le k,ai∈[ai−1+1,2ai−1]a_i \in [a_{i-1}+1,2a_{i-1}];

请你求出有多少好的正整数数列(此处数列的长度 kk 可以是任意正整数)。答案对 109+710^9+7 取模。

输入格式

本题有多组测试数据。

第一行一个正整数 qq,代表数据组数。

接下来 qq 行,每行一个正整数 nn。

输出格式

输出 qq 行,每行一个非负整数表示答案。

3
2
5
6
1
3
6
1
114514

549510777

提示

【数据范围】

对于所有数据,均有 1≤q≤641\le q \le 64,1≤n≤10181 \le n \le 10^{18}。

本题采用捆绑测试。

::cute-table{tuack} |子任务编号|分数|q=q=|n≤n\le|特殊性质| |:-:|:-:|:-:|:-:|:-:| |11|55|11|1010|无 |22|77|11|450450|无 |33|1010|11|50005000|无 |44|88|11|10610^6|无 |55|2323|11|10810^8|无 |66|33|1616|10810^8|B| |77|77|55|101810^{18}|A| |88|2525|11|101810^{18}|无 |99|33|4848|101810^{18}|B |1010|99|6464|101810^{18}|无

特殊性质 A :n=2x,x∈Z*n=2^x,x\in \mathbb{Z^{\text{*}}}

特殊性质 B :输入的 nn 递增。