生活随笔
收集整理的這篇文章主要介紹了
【UOJ #62】【UR #5】怎样跑得更快（莫比乌斯反演）
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
傳送門
以下用C,DC,DC,D表示文內(nèi)的c,dc,dc,d
顯然可以替換lcmlcmlcm后枚舉gcdgcdgcd得到
biiD≡∑d∣idC?D∑d∣j[gcd(id,jd)=1]xjjD\frac{b_i}{i^D}\equiv\sum_{d|i}d^{C-D}\sum_{d|j}[gcd(\frac i d,\frac j d)=1]x_jj^DiDbi??≡d∣i∑?dC?Dd∣j∑?[gcd(di?,dj?)=1]xj?jD
令bi=biiD,xj=xjjDb_i=\frac{b_i}{i^D},x_j=x_jj^Dbi?=iDbi??,xj?=xj?jD
bi≡∑d∣idC?D∑k∣idμ(k)∑dk∣jnxjb_i\equiv \sum_{d|i}d^{C-D}\sum_{k|\frac i d}\mu(k)\sum_{dk|j}^nx_jbi?≡d∣i∑?dC?Dk∣di?∑?μ(k)dk∣j∑n?xj?
設(shè)f(i)=∑d∣idC?Dμ(id)f(i)=\sum_{d|i}d^{C-D}\mu(\frac i d)f(i)=∑d∣i?dC?Dμ(di?)
bi≡∑d∣if(d)∑d∣jnxjb_i\equiv \sum_{d|i}f(d)\sum_{d|j}^nx_jbi?≡d∣i∑?f(d)d∣j∑n?xj?
設(shè)g(d)=∑d∣jnxjg(d)=\sum_{d|j}^nx_jg(d)=∑d∣jn?xj?
bi≡∑d∣if(d)g(d)b_i\equiv \sum_{d|i}f(d)g(d)bi?≡d∣i∑?f(d)g(d)
f(i)g(i)=bi?∑d∣i,d=?if(d)g(d)f(i)g(i)=b_i-\sum_{d|i,d\not=i}f(d)g(d)f(i)g(i)=bi??d∣i,d?=i∑?f(d)g(d)
求出ggg后考慮
g(i)=∑i∣jnxjg(i)=\sum_{i|j}^nx_jg(i)=i∣j∑n?xj?
xi=g(i)?∑i∣j,i=?jxjx_i=g(i)-\sum_{i|j,i\not=j}x_jxi?=g(i)?i∣j,i?=j∑?xj?
復(fù)雜度O(nlogn)O(nlogn)O(nlogn)
#include<bits/stdc++.h>
using namespace std
;
#define cs const
#define re register
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define fi first
#define se second
#define bg begin
cs
int RLEN
=1<<20|1;
inline char gc(){static char ibuf
[RLEN
],*ib
,*ob
;(ib
==ob
)&&(ob
=(ib
=ibuf
)+fread(ibuf
,1,RLEN
,stdin));return (ib
==ob
)?EOF:*ib
++;
}
inline int read(){char ch
=gc();int res
=0;bool f
=1;while(!isdigit(ch
))f
^=ch
=='-',ch
=gc();while(isdigit(ch
))res
=(res
+(res
<<2)<<1)+(ch
^48),ch
=gc();return f
?res
:-res
;
}
inline ll
readll(){char ch
=gc();ll res
=0;bool f
=1;while(!isdigit(ch
))f
^=ch
=='-',ch
=gc();while(isdigit(ch
))res
=(res
+(res
<<2)<<1)+(ch
^48),ch
=gc();return f
?res
:-res
;
}
inline int readstring(char *s
){int top
=0;char ch
=gc();while(isspace(ch
))ch
=gc();while(!isspace(ch
)&&ch
!=EOF)s
[++top
]=ch
,ch
=gc();return top
;
}
template<typename tp
>inline void chemx(tp
&a
,tp b
){a
<b
?a
=b
:0;}
template<typename tp
>inline void chemn(tp
&a
,tp b
){a
>b
?a
=b
:0;}
cs
int mod
=998244353;
inline int add(int a
,int b
){return (a
+=b
)>=mod
?(a
-mod
):a
;}
inline int dec(int a
,int b
){a
-=b
;return a
+(a
>>31&mod
);}
inline int mul(int a
,int b
){static ll r
;r
=1ll*a
*b
;return (r
>=mod
)?(r
%mod
):r
;}
inline void Add(int &a
,int b
){(a
+=b
)>=mod
?(a
-=mod
):0;}
inline void Dec(int &a
,int b
){a
-=b
,a
+=a
>>31&mod
;}
inline void Mul(int &a
,int b
){static ll r
;r
=1ll*a
*b
;a
=(r
>=mod
)?(r
%mod
):r
;}
inline int ksm(int a
,int b
,int res
=1){if(a
==0&&b
==0)return 0;for(;b
;b
>>=1,Mul(a
,a
))(b
&1)&&(Mul(res
,a
),1);return res
;}
inline int Inv(int x
){return ksm(x
,mod
-2);}
inline int fix(int x
){return (x
<0)?x
+mod
:x
;}
int n
,q
,c
,d
;
cs
int N
=100005;
int vis
[N
],pr
[N
],mu
[N
],tot
,f
[N
],pc
[N
],pd
[N
];
inline void init_sieve(cs
int n
=N
-5){mu
[1]=1;for(int i
=2;i
<=n
;i
++){if(!vis
[i
])pr
[++tot
]=i
,mu
[i
]=mod
-1;for(int j
=1;j
<=tot
&&i
*pr
[j
]<=n
;j
++){vis
[i
*pr
[j
]]=1;if(i
%pr
[j
]==0)break;mu
[i
*pr
[j
]]=mod
-mu
[i
];}}for(int i
=1;i
<=n
;i
++)pc
[i
]=ksm(i
,c
),pd
[i
]=ksm(i
,d
);for(int i
=1;i
<=n
;i
++){int tp
=mul(pc
[i
],Inv(pd
[i
]));for(int j
=1;i
*j
<=n
;j
++)Add(f
[i
*j
],mul(tp
,mu
[j
]));}
}
int b
[N
],g
[N
],x
[N
];
int main(){#ifdef Stargazerfreopen("lx.in","r",stdin);#endifn
=read(),c
=read(),d
=read(),q
=read();init_sieve();while(q
--){int fg
=1;for(int i
=1;i
<=n
;i
++)b
[i
]=mul(read(),Inv(pd
[i
]));for(int i
=1;i
<=n
;i
++){if(!f
[i
]&&b
[i
]){fg
=0;break;}g
[i
]=mul(Inv(f
[i
]),b
[i
]);for(int j
=2;i
*j
<=n
;j
++)Dec(b
[i
*j
],b
[i
]);}if(!fg
){puts("-1");continue;}for(int i
=n
;i
;i
--){x
[i
]=g
[i
];for(int j
=i
+i
;j
<=n
;j
+=i
)Dec(x
[i
],x
[j
]);}for(int i
=1;i
<=n
;i
++)cout
<<mul(x
[i
],Inv(pd
[i
]))<<" ";puts("");}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的【UOJ #62】【UR #5】怎样跑得更快（莫比乌斯反演）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。
