← 返回题目列表

Codeforces · 2159/E

E. 超短多项式 San

中文机器翻译题面 查看原题
这个问题在一些国家可能是众所周知的,但如果没有人提出这些问题,其他国家如何了解这些问题呢?
— 第 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 1
11
0 0
0 1
0 0
2 1
4 6
3 0
7 7
13 12
25 31
31379 9237
396176013 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。不用担心链接;那里没有什么那么有用的。相信我。