题目描述
给定正整数 $n$,定义 $f(x) = \sum_{a=1}^n\sum_{b=1}^n[ab \equiv x \pmod {n}]$。给定正整数 $K$,定义整数序列 $a_1,a_2,\cdots,a_K$ 的权值为 $\prod_{i=1}^Kf(a_i)$。对于 $r \in [0,n-1]$,定义 $g(r)$ 为所有长度为 $K$,值域为 $0,1,\cdots,n - 1$,且 $\sum_{i=1}^ka_i \equiv r \pmod{n}$ 的序列的权值之和。
你需要回答三个问题:
求出 $\sum_{i=0}^ng(i)$
求出 $\sum_{i=0}^{n-1}g(i)\cdot 3^i$
给定 $Q$ 以及 $x_1,x_2,\cdots,x_Q$,分别求出 $g(x_1),g(x_2),\cdots,g(x_Q)$。
所有问题的答案均对 $10^9 + 7$ 取模。
输入格式
正整数 $n$ 以特殊的方式给出。
第一行,一个正整数 $m$,表示 $n$ 的素因子个数。
接下来 $m$ 行:每行两个正整数 $p_i,c_i$。表示 $n = \prod_{i=1}^{n}p_i^{c_i}$。
第 $m+2$ 行:一个正整数 $K$。
第 $m+3$ 行:一个正整数 $Q$。
接下来 $Q$ 行,每行一个正整数 $x_i$。
输出格式
第一行:一个整数,表示问题 1 的答案。 第二行:一个整数,表示问题 2 的答案。 接下来 $Q$ 行:每行一个整数。表示问题 3 的答案。
样例
样例输入 1
2
2 2
3 1
2
5
0
1
2
3
4
样例输出 1
20736
355911936
2904
1152
1728
1584
2112
样例输入 2
3
2 3
3 3
5 2
10
5
0
1
2
3
4
样例输出 2
684200579
533225646
239561015
44505898
532874077
329728910
805312298
评分方式
如果输出第一行正确,则获得 $30 \%$ 的分数。 如果输出第二行正确,则获得另外 $40 \%$ 的分数。 如果输出第三至 $Q + 2$行都正确,则获得另外 $30 \%$ 的分数。
请务必保证输出恰好 $Q + 2$ 行。
数据范围
对于所有数据,满足 $2 \leq p_i < 10^9$,$p_i$ 为素数且互不相同,
$1 \leq c_i,\prod_{i=1}^m(c_i + 1),Q \leq 3 \times 10^5,1 \leq K < 10^{3 \times 10^5},0 \leq x_i < \min(n,10^{18})$
子任务编号 | 分值 | $n \leq$ | $K \leq$ |
---|---|---|---|
1 | 20 | $100$ | $10^9$ |
2 | 15 | $1000$ | |
3 | 15 | $10^6$ | $1$ |
4 | 15 | $10^8$ | |
5 | 20 | $10^{11}$ | |
6 | 15 |