链接：UOJ#62

题目描述

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

禅师浅笑，答：“方法很简单，不过若想我教你，你先看看这道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)满足：

其中(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 2
1 0 0
1 2 3

output

499122179 998244352 499122176
998244352 1 1

explanation

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

样例二

见样例数据下载。

限制与约定

对于所有数据，(ncdot q leq 3 imes 10^5)，(0 leq c, d leq 10^9)。

时间限制：1s

空间限制：256MB

后记

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

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

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

下载

样例数据下载

题目分析

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

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

设(T=kd)

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

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

则有

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

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

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

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

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

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

由

得

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

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

代码实现

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<cstdlib>
#define MAXN 0x7fffffff
typedef 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<<x[i]<<' ';cout<<'
';
}
int main(){
	n=Getint(),c=Getint()%(mod-1),d=Getint()%(mod-1),Q=Getint();
	Pre();
	while(Q--)Solve(); 
	return 0;
}