← 返回题目列表

Codeforces · 1864/H

H. 星流

中文机器翻译题面 查看原题

Bogocubic 正在和 amenotiomoi 玩游戏。首先,Bogocubic 固定了一个整数 $$$n$$$,然后他给 amenotiomoi 一个整数 $$$x$$$,它最初等于 $$$1$$$。

在一步中 amenotiomoi 以相同的概率执行以下操作之一:

- 将 $$$x$$$ 增加 $$$1$$$;
- 将 $$$x$$$ 乘以 $$$2$$$。

Bogocubic 想要找到让 $$$x$$$ 大于或等于 $$$n$$$ 所需的预期移动次数。帮助他找到这个数字对 $$$998\,244\,353$$$ 的模。

正式地,令 $$$M = 998\,244\,353$$$。可以证明,答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$y$$$,使得$$$0 \le y < M$$$ 且$$$y \cdot q \equiv p \pmod{M}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^{18}$$$)。

输出

对于每个测试用例,输出一个整数 - 预期的移动次数以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

7
1
4
8
15
998244353
296574916252563317
494288321850420024

输出 #1

0
499122179
717488133
900515847
93715054
44488799
520723508

注意

在第一个测试用例中,$$$n\le x$$$没有任何操作,所以答案是$$$0$$$。

在第二个测试用例中,对于 $$$n = 4$$$,这里是所有可能的操作序列及其概率的列表:

- $$$1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$$$,概率为$$$\frac{1}{8}$$$;
- $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{+1}{\longrightarrow}4$$$,概率为$$$\frac{1}{8}$$$;
- $$$1\stackrel{+1}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$$$,概率为$$$\frac{1}{8}$$$;
- $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{+1}{\longrightarrow}3\stackrel{\times 2}{\longrightarrow}6$$$,概率为$$$\frac{1}{8}$$$;
- $$$1\stackrel{+1}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$$$,概率为$$$\frac{1}{4}$$$;
- $$$1\stackrel{\times 2}{\longrightarrow}2\stackrel{\times 2}{\longrightarrow}4$$$,概率为 $$$\frac{1}{4}$$$。

因此,预期的移动次数为 $$$4 \cdot \left(3 \cdot \frac{1}{8}\right) + 2 \cdot \left(2 \cdot \frac{1}{4} \right) =\frac{5}{2} \equiv 499122179 \pmod{998244353}$$$。

在第三个测试用例中,对于 $$$n = 8$$$,预期的移动次数为 $$$\frac{137}{32}\equiv 717488133\pmod{998244353}$$$。

在第四个测试用例中,对于 $$$n = 15$$$,预期的移动次数为 $$$\frac{24977}{4096} \equiv 900515847 \pmod{998244353}$$$。