如约而至(walk)

LCA大佬的做法：

考虑暴力的高斯消元，我们优化它。

$\sum\limits_{j} gcd(i,j)^{c-d} i^d j^d x_j=b_i$

$\sum\limits_{j} gcd(i,j)^{c-d} y_j = \frac{b_i}{i^d}$($y_j=j^d x_j$)

那么高斯消元的矩阵的$(i,j)$位置的值就是$gcd(i,j)^{c-d}$，我们令$f(x)=x^{c-d}$

我们对于高斯消元的矩阵，只需要保留记录$D[i][i]$位置上的值就可以了。

然后当我们消到第$i$行时，有

$\begin{align*} D[i][j] &= 0 &(j \ mod \ i \ne 0) \\ D[i][j] &= g(i) &(j \ mod \ i =0) \end{align*}$

证明：

$g(i) =f(i)-\sum\limits_{t|i,t<i}g(i)$

令$d=gcd(i,j)$($j \ mod \ i \ne 0$)，此时

$D[i][j]=f(d)-\sum\limits_{t|d} g(t) = f(d)-g(d)-\sum\limits_{t|d,t<d}g(d)$

因为$g(d) = f(d) - \sum\limits_{t|d,t<d}g(d)$

所以$D[i][j]=f(d)-f(d)=0$

当$j \ mod \ i =0$时，$gcd(i,j)=i$，所以一开始的$D[i][j]$初始值一样，消的过程中减去的东西一样，所以最后的值也应该一样

//Serene

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<cstdio>

#include<cmath>

using namespace std;

#define ll long long

#define db double

#define For(i,a,b) for(int i=(a);i<=(b);++i)

#define Rep(i,a,b) for(int i=(a);i>=(b);--i)

#define getchar gc

const int maxn=1e6+7,maxt=1000+7;

const ll mod=998244353;

ll n,C,D,Td,b[maxn];

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++;

}

char cc;ll ff;

template<typename T>void read(T& aa) {

	aa=0;cc=getchar();ff=1;

	while((cc<'0'||cc>'9')&&cc!='-') cc=getchar();

	if(cc=='-') cc=getchar(),ff=-1;

	while(cc>='0'&&cc<='9') aa=aa*10+cc-'0',cc=getchar();

	aa*=ff;

}

ll qp(ll x,ll k) {

	ll rs=1;

	while(k) {

		if(k&1) rs=rs*x%mod;

		k>>=1; x=x*x%mod;

	}

	return rs;

}

ll finv(ll x) {return qp(x,mod-2);}

ll qp1(ll x,ll k) {

	if(k<0) return qp(x,k+(mod-1));

	return qp(x,k);

}

ll ans[maxn],f[maxn];

bool solve() {

	For(i,1,n) b[i]=b[i]*finv(qp(i,D));

	For(i,1,n) f[i]=qp1(i,C-D);

	For(i,1,n) {

		if(f[i]==0&&b[i]) return 0;

		else if(f[i]==0) continue;

		for(int j=i<<1;j<=n;j+=i) {

			f[j]=(f[j]-f[i]+mod)%mod;

			b[j]=(b[j]-b[i]+mod)%mod;

		}

		ans[i]=b[i]*finv(f[i])%mod;

	}

	Rep(i,n,1) {

		for(int j=i<<1;j<=n;j+=i)

			ans[i]=(ans[i]-ans[j]+mod)%mod;

	}

	For(i,1,n) ans[i]=ans[i]*finv(qp(i,D))%mod;

	return 1;

}

int main() {

	freopen("walk.in","r",stdin);

	freopen("walk.out","w",stdout);

	read(n); read(C); read(D); read(Td);

	while(Td--) {

		For(i,1,n) read(b[i]);

		if(!solve()) printf("-1");

		else For(i,1,n) printf("%lld ",ans[i]);

		printf("\n");

	}

	return 0;

}

巴特西

如约而至(walk)

最新文章

热门文章