首先讲点正常想的到的做法。
首先转化成：计数 * + * + * * + * * 的序列，要求在序列最后一个操作后恰好 \(\ge n\)，每个序列的贡献是 \(\frac{1}{2^{len}}\)。
枚举总共有多少个 *；枚举最后一个 + 之后有多少个 *。
这样，最后一个 + 的贡献是确定的，那限制就是在最后一个 + 之前要求数字达到一个范围 \([l,r]\)，则能在最后一次操作后恰好 \(\ge n\)，这个范围不难算出。
我们只需要在前面的每个 * 之前插入若干个 +，每个 + 的贡献是 \(2\) 的若干次方。也就是转化成了：选若干个 \(1,2,..,2^k\) 中的数组成一个可重集，使得和在 \([l,r]\) 内。
差分转化成求 \([0,r]\) 的答案。
考虑若干个 \(2^i\) 的数从小到大相加合并成 \(sum\) 的过程，发现这个过程是唯一的，也就是每次选出最小的 \(2^i,...,2^j (i\le j)\) 合并成一个数 \(2^k\)（如果最后 \(sum\) 包含了 \(k\) 这个二进制位）。
可以数位 dp。设 \(f(i,j,0/1)\) 表示当前决定了 sum 的最低 \(i\) 位的值，当前使用的最大数为 \(2^j\)，是否卡满上界。预处理用 \(2^i,...,2^j (i\le j)\) 合并成 \(2^k\) 的总权值即可。
一次 dp 复杂度为 \(O(\log^3 V)\)。此时发现我们不需要枚举总共有多少个 *，外层只需要枚举 \(O(\log V)\) 次，于是总复杂度 \(O(T\log^4 V)\).
接下来是 dyh 的牛逼做法。
考虑 dp 转移方程：
\(f_i = \frac{1}{2} \times f_{i/2} (i\bmod 2 \equiv 0)\)
\(f_i = \frac{1}{2} \times f_{i/2} + \frac{1}{2} f_{i-1} (i\bmod 2 \equiv 1)\)
考虑想转移 \(f_i\) 要用到什么（考虑需要记录哪些信息才能封闭）。
\(i\) 是偶数时用到 \(f_{i/2}\)；\(i\) 是奇数时用到 \(f_{i/2},f_{i-1}\)。
发先递归下去，相当于会用到所有 \(f_{\lfloor i/{2^k} \rfloor}\) 与 \(f_{\lfloor (i-1)/{2^k}\rfloor}\) 的值。
于是对于当前状态记录一个 \(\log V\) 长度的向量 \(A_i\)，表示所有的 \(f_{\lfloor i/{2^k} \rfloor}\)，为了方便设 \(f_0 = 2(f_1=\frac{1}{2}\times f_0)\)。
那么从 \(i-1\) 的向量到 \(i\) 的向量就是乘一个转移矩阵。
然后列出转移矩阵会发现，转移矩阵只和 \(i\) 的末尾 0 个数相关，也就是只有 \(\log\) 种不同的转移矩阵！（这也太神奇了）
那我们要求的就是初始向量 \(A_0\) 乘上转移矩阵的前缀积，每次询问会乘 \(\log V\) 个矩阵，复杂度 \(O(\log^3 V)\)。
转移矩阵的前缀积不难倍增预处理。时间复杂度 \(O(\log^4 V+T\log^3 V)\)。
标签：frac,log,Stream,CF1864H,Asterism,矩阵,枚举,复杂度,转移 From： https://www.cnblogs.com/Rainbowsjy/p/17860716.html