UOJ Logo Universal Online Judge

UOJ

#62. 【UR #5】怎样跑得更快

统计
$\newcommand\lcm{\mathbin{\mathrm{lcm}}}$

大力水手问禅师:“大师,我觉得我光有力气是不够的。比如我吃菠菜可以让力气更大,但是却没有提升跑步的速度。请问怎样才能跑得更快?我试过吃白菜,没有效果。”

禅师浅笑,答:“方法很简单,不过若想我教你,你先看看这道UOJ Round的C题。”

令 $p = 998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)。

给你整数 $n, c, d$。现在有整数 $x_1, \dots, x_n$ 和 $b_1, \dots, b_n$ 满足 $0 \leq x_1, \dots, x_n, b_1, \dots, b_n < p$,且对于 $1 \leq i \leq n$ 满足:

\begin{equation} \sum_{j = 1}^{n} \gcd(i, j)^c \cdot \lcm(i, j)^d \cdot x_j \equiv b_i \pmod{p} \end{equation} 其中 $v \equiv u \pmod{p}$ 表示 $v$ 和 $u$ 除以 $p$ 的余数相等。$\gcd(i, j)$ 表示 $i$ 和 $j$ 的最大公约数,$\lcm(i, j)$ 表示 $i$ 和 $j$ 的最小公倍数。

有 $q$ 个询问,每次给出 $b_1, \dots, b_n$,请你解出 $x_1, \dots, x_n$ 的值。

输入格式

第一行四个整数 $n, c, d, q$。保证 $n, q \geq 1$。

接下来 $q$ 行,每行 $n$ 个整数依次表示 $b_1, \dots, b_n$。保证 $0 \leq b_1, \dots, b_n < p$。

输出格式

共 $q$ 行,每行对给出的 $b_1, \dots, b_n$,输出对应的 $x_1, \dots, x_n$。如果有多组解输出任意一组即可。如果无解那么这一行只用输出一个整数 $-1$。

样例一

input

3 1 0 2
1 0 0
1 2 3

output

499122179 998244352 499122176
998244352 1 1

explanation

对于第一个询问,要满足的等式为:

\begin{eqnarray} \begin{cases} x_1 + x_2 + x_3 & \equiv & 1 & \pmod{p}\\ x_1 + 2x_2 + x_3 & \equiv & 0 & \pmod{p}\\ x_1 + x_2 + 3x_3 & \equiv & 0 & \pmod{p} \end{cases} \end{eqnarray}

样例二

见样例数据下载。

限制与约定

对于所有数据,$nq \leq 3 \times 10^5$,$0 \leq c, d \leq 10^9$。

测试点编号 $n$ $q$ 其他
1$\leq 3$$=1$$c, d \leq 1000$
2$\leq 100$$=1$$c = d$
3$\leq 10$保证有唯一解
4
5$\leq 1000$$c = 1, d = 0$
6保证有唯一解
7
8
9$\leq 1000$$=1$保证有唯一解
10
11
12$\leq 10$$c = d$
13保证有唯一解
14
15$\leq 10^5$$\leq 3$$c = 1, d = 0$
16
17$c = d$
18
19
20

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

后记

还没听完题,大力水手就嘶吼着:“太难了我不会我不会!”,飞快地跑掉了。

禅师看着大力水手消失的背影,叹了口气说:“你们这些人啊,每天就想做些大水题,一碰到难题,跑得不知道比谁都快。”

后来大力水手把UOJ Round的C题题面贴在了汽车的后挡风玻璃上,人类从此掌握了光速旅行的正确方式。

下载

样例数据下载