这个问题在一些国家可能是众所周知的,但如果没有人提出这些问题,其他国家如何了解这些问题呢?
— 第 21 届公开杯,东京大奖赛
给你三个整数 $$$a,b,c$$$。
设 $$$F(n)$$$ 为 $$$2n$$$ 次多项式,定义如下。
$$F(n)=\left ({a x^2+b x+c}\right) ^n$$
您需要解决以下类型的 $$$q$$$ 查询。
- $$$n\;k$$$:请求 $$$\displaystyle \sum_{i=0}^{k}{\left [ {x^i} \right] F(n)}$$$ 模 $$$10^9+7$$$$$$^{\text{*}}$$$ 的总和值。
但是,如果这个问题到此为止,对您来说可能太容易了。所以这里有一个转折$$$^{\text{†}}$$$:要求你解决问题 在线.
$$$^{\text{*}}$$$这里,$$$[x^a]F(n)$$$表示多项式$$$F(n)$$$的$$$x^a$$$的系数。
$$$^{\text{†}}$$$我希望扭转之后对你来说不会太难。即使是幼儿也知道一种解决方法。您只需将该方法优化 $$$8\,000\,000$$$ 倍即可。
输入
第一行包含三个整数 $$$a$$$、$$$b$$$、$$$c$$$ ($$$1 \le a,b,c \le 10^9+6$$$)。
第二行包含查询数量 $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$)。
$$$q$$$ 以下行中的每一行都包含两个整数 $$$n_i'$$$ 和 $$$k_i'$$$ 表示加密格式的查询。
您必须按如下方式解密查询。
- 设第 $$$i$$$ 查询模 $$$10^9+7$$$ 的答案为 $$$ans_i$$$。这里,$$$ans_0$$$ 被定义为$$$0$$$。
- 那么,第 $$$i$$$ 查询的 $$$n$$$ 和 $$$k$$$ 的值为 $$$n_i = n_i' \oplus ans_{i-1}$$$ 和 $$$k_i = k_i' \oplus ans_{i-1}$$$ ($$$0 \le n_i \le 3\cdot 10^5$$$, $$$0 \le k_i \le 2n_i$$$)。
请注意 两者 $$$n_i$$$ 的总和 和 所有查询的 $$$k_i$$$ 总和 不受限制.
输出
对于每个查询,在新行上打印对 $$$10^9+7$$$ 取模的答案。
示例
输入复制
3 2 1110 00 10 02 14 63 07 713 1225 3131379 9237396176013 396306657
输出复制
1 1 3 6 1 5 15 27 36 396240845 819003547
注意
解密示例输入如下。
3 2 1
11
0 0
1 0
1 1
1 2
2 0
2 1
2 2
2 3
2 4
31415 9265
200000 69420
这里,多项式 $$$F(n)$$$ 对应于 OEIS 中的 A084608。不用担心链接;那里没有什么那么有用的。相信我。