【UOJ#62】【UR#5】怎样跑得更快

mrsrz 9月 18, 2020

狄利克雷前缀和

题目大意：

给定 $n$ 个整数，$b_1,b_2,b_3,\ldots,b_n$，以及 $c,d$。

求一组整数 $x_1,x_2,x_3,\ldots,x_n$，使得对任意 $i\in[1,n]$，都满足：

$\sum\limits_{j=1}^n \gcd(i,j)^c\mathrm{lcm}(i,j)^dx_j\equiv b_i\pmod{998244353}$

多解输出任意一组，无解输出 -1。

题解：

首先我们有 $\gcd(i,j)\cdot\mathrm{lcm}(i,j)=ij$。令 $t=c-d$，$z=d$，$f_k(n)=n^k$。

$\sum\limits_{j=1}^n \gcd(i,j)^t\cdot i^z\cdot j^z\cdot x_j\equiv b_i\pmod{998244353}\\\sum\limits_{j=1}^n f_t(\gcd(i,j))\cdot f_z(i)\cdot f_z(j)\cdot x_j\equiv b_i\pmod{998244353}$

式子里有 $\gcd(i,j)$ 这个项，容易想到枚举这一项。但是对一个式子来说 $i$ 是确定的，所以可以想到枚举 $i$ 的因数。进一步地，我们希望能将 $f_t(n)$ 拆成和 $n$ 的因数有关的一些信息的和。

令 $f(n)$ 满足 $f_t(n)=\sum\limits_{d|n}f(d)$。

$\sum_{j=1}^n\sum_{d|i}f(d)\cdot(f_z(j)\cdot x_j)\equiv \frac{b_i}{i^z}\pmod{998244353}\\ \sum_{d|i}f(d)\cdot\sum_{j=1}^{\lfloor\frac n d\rfloor}f_z(j\cdot d)\cdot x_{jd}\equiv \frac{b_i}{i^z}\pmod{998244353}$

令 $B(n)=\frac{b_n}{n^z}$，$G(n)=\sum\limits_{n|d}f_z(d)\cdot x_d$。

$\sum_{d|n}f(d)G(d)=B(n)$

可以发现，这是个 Dirichlet 卷积的形式，已知所有 $B(i)$ 可以在 $O(n\log\log n)$ 的时间内求出所有 $f(i)G(i)$。

然后 $\sum\limits_{d|n}f(d)=f_t(n)$ 也是上面的形式，已知 $f_t$ 也可以 $O(n\log\log n)$ 求出 $f$。

而 $f_z(n)=n^z$，以及 $\frac 1{f_z(n)}=(\frac1{n})^z$这个可以在线性筛素数的同时预处理出来，时间复杂度 $O(n)$。

已知 $f(i)$ 和 $f(i)G(i)$ 后，就可以求出 $G(i)$。其中所有 $f(i)$ 的逆元可以线性处理。

然后 $G(n)=\sum\limits_{n|d}f_z(d)\cdot x_d$ 也是 Dirichlet 卷积的形式，那么 $f_z(d)\cdot x_d$ 也知道了。

则不难得到 $x$ 的值。

在本题的条件下，当且仅当上面过程中得到的 $f$ 中出现 $f(i)=0$ 的情况时才可能多解/无解。

若 $f(i)=0$ 且 $f(i)G(i)\neq 0$ 则无解。

若 $f(i)=0$ 且 $f(i)G(i)=0$，则 $G(i)$ 取任意值均可。

算法的总时间复杂度 $O(n\log\log n)$。

Code：

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int N=1e5+5,md=998244353;
inline void upd(int&a){a+=a>>31&md;}
inline int pow(int a,int b){
    int res=1;
    for(;b;b>>=1,a=(LL)a*a%md)if(b&1)res=(LL)res*a%md;
    return res;
}
int n,c,d,q,b[N],_d[N],_id[N],iv[N],F[N],tot,pri[N/7],f[N];
int pF[N],ipF[N],_F[N];
bool vis[N];
void sieve(int n){
    _d[1]=_id[1]=F[1]=1;
    for(int i=2;i<=n;++i){
        if(!vis[i])_d[i]=pow(i,d),_id[i]=pow(iv[i],d),F[i]=pow(i,c),pri[++tot]=i;
        for(int j=1;j<=tot&&i*pri[j]<=n;++j){
            vis[i*pri[j]]=1;
            _d[i*pri[j]]=(LL)_d[i]*_d[pri[j]]%md;
            _id[i*pri[j]]=(LL)_id[i]*_id[pri[j]]%md;
            F[i*pri[j]]=(LL)F[i]*F[pri[j]]%md;
            if(i%pri[j]==0)break;
        }
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>c>>d>>q;
    d%=md-1;
    c-=d;if(c<0)c+=md-1;
    iv[1]=1;
    for(int i=2;i<=n;++i)iv[i]=(LL)(md-md/i)*iv[md%i]%md;
    sieve(n);
    for(int i=tot;i;--i)
    for(int j=n/pri[i];j;--j)upd(F[j*pri[i]]-=F[j]);
    for(int i=*pF=1;i<=n;++i)pF[i]=(LL)pF[i-1]*(F[i]+!F[i])%md;
    ipF[n]=pow(pF[n],md-2);
    for(int i=n-1;~i;--i)ipF[i]=(F[i+1]+!F[i+1])*(LL)ipF[i+1]%md;
    for(int i=1;i<=n;++i)_F[i]=ipF[i]*(LL)pF[i-1]%md;
    while(q--){
        for(int i=1;i<=n;++i)cin>>b[i],b[i]=(LL)b[i]*_id[i]%md,f[i]=F[i];
        for(int i=tot;i;--i)
        for(int j=n/pri[i];j;--j)upd(b[j*pri[i]]-=b[j]);
        bool fail=0;
        for(int i=1;i<=n&&!fail;++i)if(F[i])b[i]=(LL)b[i]*_F[i]%md;
        else if(b[i])fail=1;
        if(fail){cout<<"-1\n";continue;}
        for(int i=tot;i;--i)
        for(int j=1;j*pri[i]<=n;++j)upd(b[j]-=b[j*pri[i]]);
        for(int i=1;i<=n;++i)
        cout<<(LL)b[i]*_id[i]%md<<" \n"[i==n];
    }
    return 0;
}