【UR #5】怎样跑得更快

【UR #5】怎样跑得更快

膜这个您就会了

下面是复读机mangoyang

我们要求
\[ \sum_{j=1}^n \gcd(i,j)^{c-d} j^d x_j=\frac{b_i}{i^d} \]
随便设一下

\[ \sum_{j=1}^n f(\gcd(i,j))h(j)=g(i) \\sum_{d|i}\sum_{j=1}^n [\gcd(i,j)=d]f(d)h(j)=g(i) \\sum_{d|i}\sum_{d|j}f_r(d)h(j)=g(i) \]
这里用到了第一个莫比乌斯反演，已知 \(f(d)\) 求出 \(f_r(d)\)

记 \(f_z(d)=\sum_{j=1}^n [d|j]h(j)\)
\[ \sum_{d|i} f_r(d)f_z(d)=g(i) \]
这里用第二个莫比乌斯反演，已知 \(g(i)\) 求出 \(f_r(d)f_z(d)\) ，除一下可以得到 \(f_z(d)\) 。

最后用第三个莫比乌斯反演，已知 \(f_z(d)\) 求出 \(h(j)\) 即可。

code

/*program by mangoyang*/
#pragma GCC optimize("Ofast", "inline")
#include<bits/stdc++.h>
#define inf (0x3f3f3f3f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
    int ch = 0, f = 0; x = 0;
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    if(f) x = -x;
}
const int N = 114514, mod = 998244353;
int a[N], b[N], inv1[N], inv2[N], n, q, c, d;
inline void up(int &x, int y){
    x = x + y >= mod ? x + y - mod : x + y;
}
inline int Pow(int a, int b){
    int ans = 1;
    b = (b % (mod - 1) + mod - 1) % (mod - 1);
    for(; b; b >>= 1, a = 1ll * a * a % mod)
        if(b & 1) ans = 1ll * ans * a % mod;
    return ans;
}
inline void gao1(int *a){
    for(int i = 1; i <= n; i++)
        for(int j = i + i; j <= n; j += i)
            up(a[j], mod - a[i]);
}
inline void gao2(int *a){
    for(int i = n; i >= 1; i--)
        for(int j = i + i; j <= n; j += i)
            up(a[i], mod - a[j]);
}
int main(){
    read(n), read(c), read(d), read(q);
    for(int i = 1; i <= n; i++)
        inv1[i] = Pow(i, c - d);
    for(int i = 1; i <= n; i++)
        inv2[i] = Pow(i, -d);
    gao1(inv1);
    for(int i = 1; i <= n; i++) 
        inv1[i] = Pow(inv1[i], -1);
    while(q--){
        for(int i = 1; i <= n; i++){
            read(b[i]);
            b[i] = 1ll * b[i] * inv2[i] % mod;
        }
        gao1(b);
        int flag = 0;
        for(int i = 1; i <= n; i++)
            if(!inv1[i] && b[i]){ 
                flag = 1; break; 
            }
            else b[i] = 1ll * b[i] * inv1[i] % mod;
        if(flag){
            puts("-1");
            continue;
        }
        gao2(b);
        for(int i = 1; i <= n; i++)
            b[i] = 1ll * b[i] * inv2[i] % mod;
        for(int i = 1; i <= n; i++) 
            printf("%d ", b[i]);
        puts("");
    }
    return 0;
}

【UR #5】怎样跑得更快

原文：https://www.cnblogs.com/mangoyang/p/11686022.html