推式子题,不算太难。

\[ \sum_{j=1}^{n} gcd(i, j)^c \cdot lcm(i, j)^d \cdot x_j =\sum_{j=1}^n gcd(i,j)^{c-d} i^d j^dx_j \]\(f(x)=x^{c-d}\) , \(f=g*1\) ,则有 \[ =i^d \sum_{j=1}^n \sum_{k|i,k|j} g(k) x_jj^d=i^d \sum_{k|i} g(k) \sum_{j=1}^{jk\le n} x_{jk}(jk)^d =b_i \] \(g(k) \sum_{j=1}^{jk\le n} x_{jk}(jk)^d\) 可以由 \(\frac{b_i}{i^d}\) 反演得到,\(g\) 又可以反演得到,所以 \(\sum_{j=1}^{jk\le n} x_{jk}(jk)^d\) 就求出来了。

那么 \(x_j j^d\) 也知道了,\(x\) 就求好了。

至于判无解,就是 \(\sum 0*x_i \neq 0\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=100005,P=998244353;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<1)+(res<<3)+ch-'0', ch=gc();
return res*ff;
}
LL b[maxn],g[maxn],p[maxn],mu[maxn];
bool vis[maxn];
void get_mu(){
int N=100000; mu[1]=1;
for(int i=2;i<=N;i++){
if(!vis[i]) p[++p[0]]=i, mu[i]=-1;
for(int j=1;j<=p[0]&&i*p[j]<=N;j++){
vis[i*p[j]]=true;
if(i%p[j]==0){ mu[i*p[j]]=0; break; }
mu[i*p[j]]=-mu[i];
}
}
}
LL Pow(LL a,LL b){
LL res=1;
for(;b;b>>=1,a=a*a%P) if(b&1) res=res*a%P;
return res;
}
LL n,_C,_D,Q,f[maxn],h[maxn],ipwd[maxn];

void Solve(LL a[],LL b[]){ // a = b * 1 b = a * \mu
for(int i=1;i<=n;i++) b[i]=0;
for(int i=1;i<=n;i++)
for(int j=1;i*j<=n;j++) (b[i*j]+=a[i]*(P-mu[j])%P)%=P;
}
int main(){
#ifdef LOCAL
freopen("uoj63.in","r",stdin);
freopen("uoj63.out","w",stdout);
#endif
n=getint(); _C=getint(); _D=getint(); Q=getint();
get_mu();
for(int i=1;i<=n;i++){
if(_C>_D) f[i]=Pow(i,_C-_D); else f[i]=Pow(Pow(i,_D-_C),P-2);
ipwd[i]=Pow(Pow(i,_D),P-2);
}
Solve(f,g);
while(Q--){
for(int i=1;i<=n;i++) b[i]=getint(), b[i]=b[i]*ipwd[i]%P;
Solve(b,h);
bool NoSol=false;
for(int i=1;i<=n;i++){
if(g[i]!=0) h[i]=h[i]*Pow(g[i],P-2)%P;
else if(h[i]!=0){ NoSol=true; break; }
}
if(NoSol){ printf("-1\n"); continue; }
for(int i=n;i>=1;i--)
for(int j=i+i;j<=n;j+=i) (h[i]+=P-h[j])%=P;
for(int i=1;i<=n;i++) h[i]=h[i]*ipwd[i]%P;
for(int i=1;i<=n;i++) printf("%lld ",(h[i]+P)%P); printf("\n");
}
return 0;
}