题面

链接：

题目描述

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

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

令 \(p=998244353\)（\(7×17×223+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{split} \sum_{j = 1}^{n} gcd(i, j)^c \cdot lcm(i, j)^d \cdot x_j \equiv b_i \pmod{p} \end{split} \]

其中\(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,q≥1\)。

接下来 \(q\) 行，每行 \(n\) 个整数依次表示 \(b1,…,b_n\)。保证 \(0≤b_1,…,b_n<p\)。

输出格式

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

样例一

input

3 1 0 21 0 01 2 3

output

499122179 998244352 499122176998244352 1 1

explanation

对于第一个询问，要满足的等式为：

\[ \begin{split} \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{split} \]

样例二

见样例数据下载。

限制与约定

对于所有数据，\(n\cdot q \leq 3 \times 10^5\)，\(0 \leq c, d \leq 10^9\)。

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

时间限制：1s

空间限制：256MB

后记

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

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

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

下载

题目分析

(以下式子均省略\((mod p)\))

\[ \begin{split} b_i&=\sum\limits_{j=1}^ngcd(i,j)^c\cdot lcm(i,j)^d\cdot x_j\\ &=\sum\limits_{j=1}^ngcd(i,j)^c\cdot \frac{i^d\cdot j^d}{gcd(i,j)^d}\cdot x_j\\ &=\sum\limits_{j=1}^ngcd(i,j)^{c-d}\cdot i^d\cdot j^d\cdot x_j \end{split} \]

---

设\(f(gcd(i,j))=gcd(i,j)^{c-d},h(i)=i^d,g(j)=j^d\)

\[ \begin{split} b_i&=\sum\limits_{j=1}^nf(gcd(i,j))\cdot h(i)\cdot g(j)\cdot x_j\\ &=\sum\limits_{d|i}f(d)\sum\limits_{d|j}^nh(i)\cdot g(j)\cdot x_j[\frac {gcd(i,j)}d==1]\\ &=\sum\limits_{d|i}f(d)\sum\limits_{d|j}^n\sum\limits_{k|\frac{gcd(i,j)}{d}}\mu(k)\cdot h(i)\cdot g(j)\cdot x_j\\ &=\sum\limits_{d|i}f(d)\sum\limits_{d|j}^n\sum\limits_{kd|gcd(i,j)}\mu(k)\cdot h(i)\cdot g(j)\cdot x_j\\ \end{split} \]

---

设\(T=kd\)

\[ \begin{split} \frac {b_i}{h(i)}&=\sum\limits_{T|i}\sum\limits_{T|j}^n\sum\limits_{d|T}\mu(\frac Td)g(j)\cdot x_j\cdot f(d)\\ &=\sum\limits_{T|i}\sum\limits_{T|j}^ng(j)\cdot x_j \sum\limits_{d|T}\mu(\frac Td)f(d) \end{split} \]

你发现\(\sum\limits_{d|T}\mu(\frac Td)f(d)\)是一个可以\(O(n\log n)\)预处理出的函数，设为\(fr(T)\)

\[ \begin{split} \frac {b_i}{h(i)}&=\sum\limits_{T|i}\sum\limits_{T|j}^ng(j)\cdot x_j\cdot fr(T)\\ &=\sum\limits_{T|i}fr(T)\sum\limits_{T|j}^ng(j)\cdot x_j \end{split} \]

---

设\(q(T)=\sum\limits_{T|j}^ng(j)\cdot x_j,F(T)=q(T)\cdot fr(T),w(i)=\frac {b_i}{h(i)}\)

则有

\[ \begin{split} w(i)=\sum\limits_{T|i}F(T) \end{split} \]

这是一个莫比乌斯反演的模型，可以化为

\[ F(i)=\sum\limits_{T|i}\mu(\frac iT)w(T) \]

现在，\(F(i)\)已经可以\(O(n \log n)\)预处理出，所以再反代回去

\[ \begin{split} q(i)\cdot fr(i)&=F(i)\\ q(i)&=\frac {F(i)}{fr(i)}\\ \end{split} \]

此时，由于\(F(i),fr(i)\)均可预处理，\(q(i)\)也相当于可以预处理出。

---

设\(t(j)=g(j)\cdot x_j\)，则有

\[ q(i)=\sum\limits_{i|j}^nt(j) \]

这又是一个莫比乌斯反演的模型，可以化为

\[ t(i)=\sum\limits_{i|j}^n\mu(\frac ji)q(j) \]

这样一来，\(t(i)\)也可以\(O(n \log n)\)预处理出。

---

由

\[ t(i)=g(i)\cdot x_i \]

得

\[ x_i=\frac{t(i)}{g(i)} \]

---

只要每个询问都\(O(n \log n)​\)完成预处理，便可以\(O(1)​\)求得答案。

对于无解的情况，只用判断是否有非零数除以零即可。

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define MAXN 0x7ffffffftypedef long long LL;const int N=100005,mod=998244353;using namespace std;inline int Getint(){register int x=0,f=1;register char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}return x*f;}int mu[N],prime[N];bool vis[N];LL ksm(LL x,LL k){ LL ret=1; while(k){ if(k&1)ret=ret*x%mod; x=x*x%mod,k>>=1; } return ret;}int n,c,d,Q;int f[N],g[N],h[N],b[N];int fr[N],w[N],F[N];int q[N],t[N],x[N];void Pre(){ for(int i=1;i<=n;i++){ f[i]=ksm(i,(c-d+(mod-1))%(mod-1)); h[i]=g[i]=ksm(i,d); } mu[1]=1; for(int i=2;i<=n;i++){ if(!vis[i])prime[++prime[0]]=i,mu[i]=-1; for(int j=1;j<=prime[0]&&1ll*i*prime[j]<=n;j++){ vis[i*prime[j]]=1; if(i%prime[j]==0)break; mu[i*prime[j]]=-mu[i]; } } for(int i=1;i<=n;i++){ for(int j=i;j<=n;j+=i){ fr[j]=(fr[j]+mu[j/i]*f[i])%mod; } fr[i]=(fr[i]+mod)%mod; }} void Solve(){ for(int i=1;i<=n;i++)b[i]=Getint(); for(int i=1;i<=n;i++)w[i]=b[i]*ksm(h[i],mod-2)%mod; memset(F,0,sizeof(F)); for(int i=1;i<=n;i++){ for(int j=i;j<=n;j+=i){ F[j]=(F[j]+mu[j/i]*w[i])%mod; } F[i]=(F[i]+mod)%mod; } for(int i=1;i<=n;i++){ if(F[i]!=0&&fr[i]==0){puts("-1");return;} q[i]=F[i]*ksm(fr[i],mod-2)%mod; } for(int i=1;i<=n;i++){ t[i]=0; for(int j=i;j<=n;j+=i){ t[i]=(t[i]+mu[j/i]*q[j])%mod; } t[i]=(t[i]+mod)%mod; } for(int i=1;i<=n;i++){ if(t[i]!=0&&g[i]==0){puts("-1");return;} x[i]=t[i]*ksm(g[i],mod-2)%mod; } for(int i=1;i<=n;i++)cout<
           
            <<' ';cout<<'\n';}int main(){ n=Getint(),c=Getint()%(mod-1),d=Getint()%(mod-1),Q=Getint(); Pre(); while(Q--)Solve(); return 0;}