分析：看到$\sum i*b_i$的式子以及每次传球向右移动一位，很容易想到HNOI2017项链的循环卷积。假设我们用FFT处理出来了每个环传0次，传1次，传2次，...，传环的大小n-1次对应的结果。那么对于每个询问k，只需要对于每个环，找出k模环的大小对应的答案即可。但是如果对每个环都找，时间复杂度是吃不消的。所以采用分块的方法，对于小于$\sqrt(n)$的环，把答案加进一个预处理数组中，对于大于$\sqrt(n)$的环，直接枚举所有询问，把结果加进去。最后再对每个询问枚举小于$\sqrt(n)$的环的累计答案。
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 102000; 5 const int mod1 = 998244353; 6 const int mod2 = 1004535809; 7 8 int n,m,num; 9 int p[maxn],vis[maxn],query[maxn]; 10 vector<int> vec; 11 vector<int> ans1[500]; // xiaoyu sqrtn de daan 12 vector<int> ans2[500]; 13 14 int res1[maxn],res2[maxn]; //zuizhongdaan 15 16 int A[maxn*16],B[maxn*16],C[maxn*16]; 17 int r[maxn*16],len = 1,bit=0; 18 void build_P(){ 19 for(int i=0;i<9*num;i++) A[i] = B[i] = C[i] = 0; 20 for(int i=0;i<num;i++) A[num-i-1] = vec[i]; 21 for(int i=0;i<num;i++) B[i] = B[num+i] = vec[i]; 22 } 23 24 int fast_pow(int dt,int pw,int mod){ 25 int res=1,now=dt,p=1; 26 while(p<=pw){ 27 if(p&pw) res = 1ll*res*now%mod; 28 now=1ll*now*now%mod; 29 p<<=1; 30 } 31 return res; 32 } 33 34 void FFT(int *a,int flag,int mod){ 35 for(int i=0;i<len;i++) if(i < r[i]) swap(a[i],a[r[i]]); 36 for(int mid = 1;mid<len;mid<<=1){ 37 int nw = fast_pow(3,(mod-1)/(2*mid),mod); 38 if(flag == -1) nw = fast_pow(nw,mod-2,mod); 39 for(int i=0;i<len;i+=(mid<<1)){ 40 int tmp = 1; 41 for(int j=0;j<mid;j++,tmp=1ll*tmp*nw%mod){ 42 int x = a[i+j],y=1ll*tmp*a[i+j+mid]%mod; 43 a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod; 44 } 45 } 46 } 47 if(flag == -1){ 48 int dt = fast_pow(len,mod-2,mod); 49 for(int i=0;i<len;i++){ 50 a[i] = 1ll*a[i]*dt%mod; 51 } 52 } 53 } 54 55 void fft(int mod){ 56 len = 1,bit = 0; 57 while(len < 4*num){len<<=1,bit++;} 58 for(int i=0;i<len;i++) r[i] = (r[i>>1]>>1)|((i&1)<<(bit-1)); 59 FFT(A,1,mod); FFT(B,1,mod); 60 for(int i=0;i<len;i++) C[i] = 1ll*A[i]*B[i]%mod; 61 FFT(C,-1,mod); 62 } 63 64 long long xxx,yyy; 65 void exgcd(int a,int b){ 66 if(!b){ 67 xxx=1;yyy=0;return; 68 } 69 exgcd(b,a%b); 70 long long t = xxx; xxx = yyy; yyy = t-a/b*yyy; 71 } 72 73 long long fast_mul(long long dt,long long pw,long long mod){ 74 long long res=0,now=dt,p=1; 75 while(p<=pw){ 76 if(p&pw) res = (res+now)%mod; 77 now=(now+now)%mod; 78 p<<=1; 79 } 80 return res; 81 } 82 83 long long merge(int b,int d){ 84 long long mod = 1ll*mod1*mod2; 85 long long as; 86 if(d-b > 0){ 87 as = fast_mul(fast_mul(xxx,(d-b),mod),mod1,mod)+b; 88 as %= mod; 89 as += mod; as%= mod; 90 }else{ 91 long long xx = -xxx; 92 as = fast_mul(fast_mul(xx,b-d,mod),mod1,mod)+b; 93 as %= mod; 94 as += mod; as%= mod; 95 } 96 return as; 97 } 98 99 int main(){ 100 //freopen("1.in","r",stdin); 101 ios::sync_with_stdio(false); 102 cin >> n >> m; 103 for(int i=1;i<=n;i++){ 104 cin >> p[i]; 105 } 106 for(int i=1;i<=m;i++) cin >> query[i]; 107 108 for(int i=1;i*i<=n;i++){ 109 for(int j=0;j<i;j++) ans1[i].push_back(0),ans2[i].push_back(0); 110 } 111 112 for(int i=1;i<=n;i++){ 113 if(!vis[i]){ 114 int j = i;vec.clear();num = 0; 115 while(!vis[j]){num++;vec.push_back(j);vis[j]=1;j = p[j];} 116 build_P(); 117 fft(mod1); 118 if(num*num <= n){ 119 for(int j=0;j<num;j++){ 120 ans1[num][j]+=C[num-1+j]; 121 ans1[num][j]%=mod1; 122 } 123 }else{ 124 for(int j=1;j<=m;j++){ 125 int dt = query[j]%num; 126 res1[j] += C[num-1+dt]; 127 res1[j]%=mod1; 128 } 129 } 130 build_P(); 131 fft(mod2); 132 if(num*num <= n){ 133 for(int j=0;j<num;j++){ 134 ans2[num][j]+=C[num-1+j]; 135 ans2[num][j]%=mod2; 136 } 137 }else{ 138 for(int j=1;j<=m;j++){ 139 int dt = query[j]%num; 140 res2[j] += C[num-1+dt]; 141 res2[j]%=mod2; 142 } 143 } 144 } 145 } 146 for(int i=2;i*i<=n;i++){ 147 for(int j=1;j<=m;j++){ 148 res1[j] += ans1[i][query[j]%i]; 149 res1[j]%=mod1; 150 res2[j] += ans2[i][query[j]%i]; 151 res2[j]%=mod2; 152 } 153 } 154 exgcd(mod1,mod2); 155 for(int i=1;i<=m;i++){ 156 //cout<<res1[i]<<" "<<res2[i]<<endl; 157 cout<<merge(res1[i],res2[i])<<endl; 158 } 159 return 0; 160 }