Description

3.1 Background
春日的山中灌木茂盛，幾乎長到了人的腰間，將山間都鋪滿了綠色。雨后的灌木之間還帶著晨露，總會(huì)沾濕走過的行人的衣裳。
林中枝葉茂密，不過樹木長的并不緊，遮不住天上，陽光落下照在山路上的灌木叢和落葉上。
山的另一側(cè)，是漫山的花樹，覆蓋在山上，一直蔓延到山下，白瓣在微暖的陽光里透著粉紅。風(fēng)吹過，成片的花樹搖動(dòng)，花瓣翻飛而起，飄散開來，叫人移不開眼睛……
呵……這漫山的花樹，叫小S怎能去雨露均沾呢……

3.2 Piece雨露均沾是不可能的，這輩子都不可能的，人力氣又小，只能待到山花爛漫時(shí)，自取那滿山爛漫來。3.3 Description今天又是去采花的好日子啊～～小S站在山頂，發(fā)現(xiàn)今日的花樹們，在不甚平坦的山上，煥發(fā)出了別樣的光彩。簡(jiǎn)單來說，它們組成了一棵以1為根的樹（QuQ…每棵花樹上有若干朵花，具體的，在編號(hào)為i的花樹上有ai朵花。山花自然是越多越好，但小S卻做不到雨露均沾…為了維護(hù)山間的生態(tài)多樣性和自己的名譽(yù)和精力

小S決定從某一個(gè)節(jié)點(diǎn)u開始對(duì)其子樹中與u距離小于K的節(jié)點(diǎn)代表的花樹進(jìn)行采摘。
特別的，節(jié)點(diǎn)u代表的花樹也會(huì)被采摘。
依舊受限于精力，小S并不會(huì)親自去采摘而是使用Extremely Strong的工具進(jìn)行采摘。
我們定義一個(gè)工具的能力為c，小S會(huì)采摘的山樹集合為T
那么小S能采摘到的山花數(shù)量fT = Πi∈T (ai
, c)
現(xiàn)在對(duì)于給定的樹和閥值K，小S想要知道每一組詢問的fT

Input

第一行，三個(gè)正整數(shù)n, Q, K，代表花樹的棵數(shù)，詢問次數(shù)和閥值。
接下來一行n個(gè)正整數(shù)，其中第i個(gè)數(shù)代表編號(hào)為i的花樹的花的個(gè)數(shù)ai。
接下來n?1行，描述了花樹們所形成的那棵樹，每行兩個(gè)正整數(shù)u, v，代表編號(hào)為u和v的花樹直接相連。
接下來Q行，每行描述了一次詢問，包含兩個(gè)正整數(shù)x, c代表這次小S決定從編號(hào)為x的花樹開始采摘，這次工具的能力為c。

Output

共Q行，每行一個(gè)整數(shù)ans，滿足ans ≡ fi (mod 998244353)其中fi為第i次詢問的答案，即能采摘到的山花數(shù)量

Sample Input

4 2 2
6 25 12 5
1 2
1 3
2 4
1 5
4 5

Sample Output

5
5

Data Constraint

Sample Inputx & Outputx
見選手下發(fā)文件中C_ex0.in/ans，C_ex1.in/ans。

Solution

• 顯然我們可以對(duì)于每個(gè)質(zhì)因子分開考慮。

• 離線算出每個(gè)質(zhì)因子對(duì)詢問的貢獻(xiàn)，那么乘起來就得到每個(gè)詢問的答案了。

• 因?yàn)?#xff1a;$$2?3?5?7?11?13?17?19=9699690<10^7$$

• 所以一個(gè)數(shù)不同的質(zhì)因子個(gè)數(shù)最多為 $8$ ，近似于一個(gè) $log$。

• 那么我們枚舉一個(gè)質(zhì)因子 $p$，考慮計(jì)算其貢獻(xiàn)的答案。

• 我們把含有 $p$ 的 $a_i$ 和詢問$c$ 都拿出來，按其中含有 $p$ 的個(gè)數(shù)從小到大排序（$a_i=a?p^k$）。

• 從左到右掃，那么對(duì)于一個(gè)詢問，它前面的 $a_i$ 與自己做 gcd 時(shí)得到 $k$ 的個(gè)數(shù)肯定小于自己。

• 相反的，后面的 $a_i$ 與自己的 gcd 得到 $k$ 的個(gè)數(shù)肯定大于等于自己。

• 于是我們算出前面 $k$ 的和、加上后面 $a_i$ 的個(gè)數(shù)乘上自己的 $k$ 個(gè)數(shù)（記為 $sum$），

• 就得到了關(guān)于這個(gè)詢問的貢獻(xiàn)，即乘上 $p^{sum}$ 。

• 我們?nèi)绾谓y(tǒng)計(jì)哪些 $a_i$ 能被計(jì)算進(jìn)詢問呢？用dfs序呀！

• 在 $x$ 點(diǎn)處打上+1標(biāo)記，在 $x$ 的 $K$ 級(jí)祖先處打上-1標(biāo)記，用樹狀數(shù)組查詢一段區(qū)間即可。

• 開始時(shí)我們需要將每個(gè) $a_i$ 分解質(zhì)因數(shù)，我們可以先線篩出 $10^7$ 以內(nèi)的質(zhì)數(shù)。

• 這里有個(gè)小技巧，篩的時(shí)候不是從 $i$ 篩掉 $i?f[j]$ 嗎？

• 我們?cè)O(shè)一個(gè)數(shù)組 $pre$ ，使得 $pre[i?f[j]]=f[j]$ ，那么我們順著 $pre[a_i]$ 就能將 $a_i$ 分解了。

• 那么時(shí)間復(fù)雜度為 $O(nlo{g}^{2}n)$ 。

Code

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cctype> using namespace std; typedef long long LL; const int N=1e5+5,M=1e7+5,mo=998244353; struct data {int x,y,z; }b[N<<1],c[N],t; int n,q,k,tot; int first[N],nex[N<<1],en[N<<1]; int a[N],f[N*7],pre[M],g[N*7]; int ans[N],dfn[N],size[N],fa[N],st[N],hl[N],hr[N],pos[M]; int vis[M],val[M]; bool bz[M]; vector<data>ss[N*7]; inline int read() {int X=0,w=0; char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();return w?-X:X; } void write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline void insert(int x,int y) {nex[++tot]=first[x];first[x]=tot;en[tot]=y; } void dfs(int x,int y,int z) {dfn[x]=++tot;size[x]=1;st[z]=x;if(z>k) fa[x]=st[z-k];for(int i=first[x];i;i=nex[i])if(en[i]^y){dfs(en[i],x,z+1);size[x]+=size[en[i]];} } inline bool cmp(data x,data y) {return x.y<y.y; } inline void changel(int x,int y) {while(x<=n) hl[x]+=y,x+=x&-x; } inline int findl(int x) {int sum=0;while(x) sum+=hl[x],x-=x&-x;return sum; } inline void changer(int x,int y) {while(x<=n) hr[x]+=y,x+=x&-x; } inline int findr(int x) {int sum=0;while(x) sum+=hr[x],x-=x&-x;return sum; } inline int ksm(int x,int y) {int s=1;while(y){if(y&1) s=(LL)s*x%mo;x=(LL)x*x%mo;y>>=1;}return s; } int main() {freopen("C.in","r",stdin);freopen("C.out","w",stdout);n=read(),q=read(),k=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<n;i++){int x=read(),y=read();insert(x,y);insert(y,x);}tot=0;dfs(1,0,1);for(int i=2;i<M;i++){if(!bz[i]) f[++f[0]]=i;for(int j=1;j<=f[0] && i*f[j]<M;j++){bz[i*f[j]]=true;pre[i*f[j]]=f[j];if(i%f[j]==0) break;}}for(int i=1;i<=q;i++){c[i].x=read(),c[i].y=read(),c[i].z=i;ans[i]=1;}memset(bz,false,sizeof(bz));tot=0;for(int i=1;i<=n;i++){int x=a[i];tot++;st[0]=0;while(pre[x]){if(vis[pre[x]]<tot){vis[pre[x]]=tot;st[++st[0]]=pre[x];val[pre[x]]=0;}val[pre[x]]++;if(!bz[pre[x]]){bz[pre[x]]=true;g[++g[0]]=pre[x];pos[pre[x]]=g[0];}x/=pre[x];}if(vis[x]<tot){vis[x]=tot;st[++st[0]]=x;val[x]=0;}val[x]++;if(!bz[x]){bz[x]=true;g[++g[0]]=x;pos[x]=g[0];}for(int j=1;j<=st[0];j++)ss[pos[st[j]]].push_back((data){i,val[st[j]],0});}for(int i=1;i<=q;i++){int x=c[i].y;tot++;st[0]=0;while(pre[x]){if(vis[pre[x]]<tot){vis[pre[x]]=tot;st[++st[0]]=pre[x];val[pre[x]]=0;}val[pre[x]]++;x/=pre[x];}if(vis[x]<tot){vis[x]=tot;st[++st[0]]=x;val[x]=0;}val[x]++;for(int j=1;j<=st[0];j++) ss[pos[st[j]]].push_back((data){c[i].x,val[st[j]],i});}for(int p0=1;p0<=g[0];p0++){int p=g[p0],cnt=tot=0;for(int i=0;i<(int)ss[p0].size();i++){b[++tot]=ss[p0][i];if(b[tot].z) cnt++;}if(!cnt) continue;sort(b+1,b+1+tot,cmp);for(int i=1;i<=tot;i++)if(!b[i].z){changer(dfn[b[i].x],1);if(fa[b[i].x]) changer(dfn[fa[b[i].x]],-1);}int sum1=0,sum2=0;for(int i=1;i<=tot;i++)if(!b[i].z){changel(dfn[b[i].x],b[i].y);changer(dfn[b[i].x],-1);if(fa[b[i].x]){changel(dfn[fa[b[i].x]],-b[i].y);changer(dfn[fa[b[i].x]],1);}}else{int sum1=findl(dfn[b[i].x]+size[b[i].x]-1)-findl(dfn[b[i].x]-1);int sum2=findr(dfn[b[i].x]+size[b[i].x]-1)-findr(dfn[b[i].x]-1);int sum=(sum1+(LL)sum2*b[i].y)%mo;ans[b[i].z]=(LL)ans[b[i].z]*ksm(p,sum)%mo;}for(int i=1;i<=tot;i++)if(!b[i].z){changel(dfn[b[i].x],-b[i].y);if(fa[b[i].x]) changel(dfn[fa[b[i].x]],b[i].y);}}for(int i=1;i<=q;i++) write(ans[i]),putchar('\n');return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5930. 【NOIP2018模拟10.26】山花的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。