uoj62 怎样跑得更快

发表于 | 更新于

Link

给定n,c,d,P=998244353,b1,...,bn∈[1,P)n,c,d,P=998244353,b_1,...,b_n\in[1,P)，

解出x1,...,xnx_1,...,x_n满足

Solution

搞出一个辅助函数g(x)g(x)满足

f(x)=∑d∣xg(d)f(x)=\sum_{d|x}g(d)

代入有

设

h(d)=∑d∣ixi′h(d)=\sum\limits_{d|i}x'_i

则

求出来g(i)h(i)g(i)h(i)就有了h(i)h(i)

有了h(i)h(i)我感觉已经忘了一开始要求什么了。。

哦对了

h(d)=∑d∣ixi′h(d)=\sum_{d|i}x'_i

Tips

一定要弄清反演的方向！！！

Code

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
struct Istream {
	Istream() {
#ifndef ONLINE_JUDGE
#ifdef DEBUG
		freopen("input","r",stdin);
#else
		std::string fileName(__FILE__),name=fileName.substr(0,fileName.find('.'));
		freopen((name+".in").c_str(),"r",stdin);
		freopen((name+".out").c_str(),"w",stdout);
#endif
#endif
	}
	template <class T> 
	Istream &operator >>(T &x) {
		static char ch;static bool neg;
		for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
		for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
		x=neg?-x:x;
		return *this;
	}
}is;
struct Ostream {
	template <class T>
	Ostream &operator <<(T x) {
		x<0 && (putchar('-'),x=-x);
		static char stack[233];static int top;
		for(top=0;x;stack[++top]=x%10+'0',x/=10);
		for(top==0 && (stack[top=1]='0');top;putchar(stack[top--]));
		return *this;
	}
	Ostream &operator <<(char ch) {
		putchar(ch);
		return *this;
	}
}os;
#define int64 long long
const int P=(7*17<<23)+1,MAXN=1e5+11;
int64 Pow(int64 base,int index,int P) {
	static int64 res;
	(index%=P-1)<0 && (index+=P-1);
	for(res=P!=1,base%=P;index;index&1 && ((res*=base)%=P),index>>=1,(base*=base)%=P);
	return res;
}
int Inverse(int x,int P) {
	return Pow(x,P-2,P);
}
int main() {
	int n,c,d,Q;
	is>>n>>c>>d>>Q;
	static int64 g[MAXN],f[MAXN],ig[MAXN],inv[MAXN];
	for(int i=1;i<=n;++i) {
		inv[i]=Inverse(i,P);
		(g[i]+=(f[i]=Pow(i,c-d,P)))%=P;
		ig[i]=Inverse(g[i],P);
		for(int j=i*2;j<=n;j+=i) {
			(g[j]-=g[i])%=P;
		}
	}
	for(int rep=1;rep<=Q;++rep) {
		static int64 b[MAXN],h[MAXN],gh[MAXN],x[MAXN];
		for(int i=1;i<=n;++i) {
			is>>b[i];
			(b[i]*=Pow(inv[i],d,P))%=P;
		}
		for(int i=1;i<=n;gh[i]=b[i],++i);
		bool tak=1;
		for(int i=1;i<=n;++i) {
			for(int j=i*2;j<=n;j+=i) {
				(gh[j]-=gh[i])%=P;
			}
			if(gh[i] && !g[i]) {
				tak=0;
				break;
			} else {
				h[i]=gh[i]*ig[i]%P;
			}
		}
		if(tak==0) {
			os<<-1<<'\n';
		} else {
			for(int i=1;i<=n;x[i]=h[i],++i);
			for(int i=n;i>=1;--i) {
				for(int j=i*2;j<=n;j+=i) {
					(x[i]-=x[j])%=P;
				}
			}
			for(int i=1;i<=n;++i) {
				(x[i]*=Pow(inv[i],d,P))%=P;
				x[i]<0 && (x[i]+=P);
				os<<x[i]<<(i==n?'\n':' ');
			}
		}
	}
	return 0;
}