【题解】[UR#5 C]怎样跑的更快

给定 $n ≤ 10^5;c,d ≤ 10^9$ 。

现有长度为 $n$ 的序列 $b$ 满足 $b_{i} \equiv \sum_{i=1}^{n} \operatorname{gcd}(i, j)^{c} \mathrm{lcm}(i, j)^{d} z_{j}(\bmod 998244353)$ 。

求 $\{z_n\}$ 。

草,这真是一道神仙题。钛钛钛钛有趣辣!sto vfk .

先转化一下:

考虑形如 $\sum_{j=1}^{n}f(\gcd(i,j))\cdot g(i)\cdot h(j)\cdot z_j$ 等于某个值的东西,大概都是可做的。考虑先构造一个 $f’$ 满足

那么就可以化一下

那么就相当于要验证

如果能快速算 $\zeta(d)=\sum_{j=1}^n[d|j]\cdot h(j)\cdot z_j $ 的话,那么有

考虑对于一个二元关系

这东西,知道 $q$ 之后是可以很容易地容斥出 $p$ 的。那么也就是说可以很容易地得到 $f’(k)\zeta(k)$ 。那么同时由于知道了 $f(k)=k^{c-d}$ ,是很容易直接容斥出 $f’(k)$ 的。也就是现在 $\zeta$ 变成了已知。

考虑如何从 $\zeta(d)=\sum_{j=1}^n[d|j]\cdot h(j)\cdot z_j $ 反推出 $z_j$ 来,发现本质上是这样的:

根据莫比乌斯反演的另一种形式

反演一下变成

然后就可以直接做了。

注意到以上每个推完的式子,求的时候都是 $nH(n)$ 的复杂度,$O(n\ln n)$ 。

神题神题,可能这是我接触过的最像莫比乌斯反演的莫比乌斯题。并且把反演的容斥作用很好地诠释了出来。

还有注意无解的情况,由于 $0$ 不存在逆元,所以在求逆元的时候需要判一下是否存在「求了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
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
97
98
99
100
101
102
103
104
105
106
#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;

void debug(int *tp, int minn, int maxn, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << " " ; cout << c ;
}

const int N = 200010 ;

const int P = 998244353 ;

int q ;
int b[N] ;
int g[N] ;
int f[N] ;
int hz[N] ;
int ans[N] ;
int n, c, d ;
int base[N] ;
int zeta[N] ;
int fzeta[N] ;

void add(int &a, int b){
a += b ;
if (a > P) a -= P ;
}
void dec(int &a, int b){
(a -= b) %= P ;
if (a < 0) a += P ;
}
int expow(int a, int b){
int res = 1 ;
if (b < 0) b += (P - 1) ;
while (b){
if (b & 1)
res = (ll)res * a % P ;
a = (ll)a * a % P ; b >>= 1 ;
}
return res ;
}
namespace Linear_s{
int cnt ;
int pr[N] ;
int mu[N] ;
int smu[N] ;
int vis[N] ;
vector <int> fc[N] ;
void sieve(int U){
mu[1] = 1 ;
for (int i = 2 ; i <= U ; ++ i){
if (!vis[i]) mu[i] = -1, pr[++ cnt] = i ;
for (int j = 1 ; j <= cnt ; ++ j){
if (i * pr[j] > U) break ;
vis[i * pr[j]] = 1 ;
if (i % pr[j] == 0) break ;
mu[i * pr[j]] = -mu[i] ;
}
}
for (int i = 1 ; i <= U ; ++ i)
smu[i] = smu[i - 1] + mu[i] ;
for (int i = 1 ; i <= U ; ++ i)
for (int j = 1 ; i * j <= U ; ++ j)
fc[i * j].push_back(i) ;
}
}
int main(){
ios::sync_with_stdio(0) ;
using namespace Linear_s ;
cin.tie(0) ; cout.tie(0) ;
cin >> n >> c >> d >> q ; sieve(n + 10) ;
for (int i = 1 ; i <= n ; ++ i)
g[i] = expow(i, d), f[i] = expow(i, c - d) ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 2 ; i * j <= n ; ++ j)
dec(f[i * j], f[i]) ;
while (q --){
int hasans = 1 ;
for (int i = 1 ; i <= n ; ++ i)
cin >> b[i], hz[i] = 0 ;
for (int i = 1 ; i <= n ; ++ i)
base[i] = (ll)expow(g[i], P - 2) * b[i] % P ;
for (int i = 1 ; i <= n ; ++ i) fzeta[i] = base[i] ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 2 ; i * j <= n ; ++ j)
dec(fzeta[i * j], fzeta[i]) ;
for (int i = 1 ; i <= n ; ++ i)
if (!f[i] && fzeta[i]) { hasans = 0 ; break ; }
if (!hasans) { cout << "-1" << '\n' ; continue ; }
//debug(fzeta, 1, n, '\n') ;
for (int i = 1 ; i <= n ; ++ i)
zeta[i] = (ll)fzeta[i] * expow(f[i], P - 2) % P ;
for (int i = 1 ; i <= n ; ++ i)
for (int j = 1 ; i * j <= n ; ++ j)
add(hz[i], (mu[j] * zeta[i * j] % P + P) % P) ;
//debug(zeta, 1, n, '\n') ;
for (int i = 1 ; i <= n ; ++ i)
ans[i] = (ll)hz[i] * expow(g[i], P - 2) % P ;
for (int i = 1 ; i <= n ; ++ i)
cout << ans[i] << " \n"[i == n] ;
}
return 0 ;
}