为了方便，将最终答案乘上$2^{k}$，即不考虑每一次均分时除以$2$
记$2^{t}\mid\mid n$和$m=\lceil\frac{n}{2^{t+1}}\rceil$，并对询问的$k$分类讨论：
1.当$k\le t$时，暴力预处理出答案即可，时间复杂度为$o(n\log n)$
2.当$k>t$时，观察可得序列总形如$\{z_{1}^{2^{t+1}},z_{2}^{2^{t+1}},...,z_{m}^{2^{t}}\}$（幂次指重复次数）
同时，对其操作后，有$\{z'_{i}\}=\{z_{1}+z_{m},z_{1}+z_{m-1},...,2z_{\lceil\frac{mid}{2}\rceil}\}$
考虑差分序列$\Delta z_{i}=z_{i+1}-z_{i}$，则操作后$\{\Delta z'_{i}\}=\{-\Delta z_{m-1},\Delta z_{1},...,(-1)^{m-1}\Delta z_{\lfloor\frac{m}{2}\rfloor}\}$
构造$\{Z_{i}\}=\{\Delta z_{i},-\Delta z_{m-1},-\Delta z_{m-2},...,-\Delta z_{1}\}$，则操作即置换$f_{i}=\begin{cases}2i&i
根据元素和，可以解得$z_{1}=\frac{2^{k}\sum_{i=1}^{n}a_{i}-\sum_{i=1}^{m-1}(n-i\cdot 2^{t+1})Z_{i}}{n}$，进而$z_{\lfloor\frac{x-1}{2^{t+1}}\rfloor+1}=z_{1}+\sum_{j=1}^{\lfloor\frac{x-1}{2^{t+1}}\rfloor}Z_{j}$
记$Z_{i}$的系数为$g_{i}$，则答案即$\frac{\sum_{i=1}^{n}a_{i}}{n}+\frac{\sum_{i=1}^{m}g_{i}f^{k-t-1}(Z0)_{i}}{2^{k}}$（其中$\{Z0_{i}\}$为$k=t+1$时的$\{Z_{i}\}$）
前者可以直接处理，后者将$f$拆为若干个置换环，并用NTT求出对模环长每个余数的贡献
同时，注意到$f_{i}\equiv 2i(mod\ 2m-1)$，记$l$为$2$模$2m-1$的阶，则所有置换环长度均是$l$的约数
换言之，置换环仅有$\sigma(l)$种长度，对于每种长度内部求和后$o(l)$统计对模$l$每个余数的贡献
另外，询问时有两个细节：1.分块$o(1)$求$2^{k}$的逆元（类似BSGS）；2.特判$m=1$的情况
总复杂度为$o(n\log n+n\sigma(l)+q)$，可以通过
1 #include
2 using namespace std;
3 #define N 2100005
4 #define K 35000
5 #define mod 998244353
6 #define ll long long
7 #define ull unsigned ll
8 int T,n,q,x,t,m,l,rev[N<<1],vis[N],f[N];
9 int inv,sum,pw[K],PW[K],a[N<<1],b[N<<1],z[N],Z[N],g[N],ans1[30],ans2[N];
10 ll k0,k,ans;ull seed;vector<int>v,Ans[N];
11 int read(){
12 int x=0;char c=getchar();
13 while ((c<'0')||(c>'9'))c=getchar();
14 while ((c>='0')&&(c<='9'))x=x*10+c-'0',c=getchar();
15 return x;
16 }
17 ull rd(ull &x){
18 x^=(x<<13),x^=(x>>7),x^=(x<<17);
19 return x;
20 }
21 int qpow(int n,int m){
22 int s=n,ans=1;
23 while (m){
24 if (m&1)ans=(ll)ans*s%mod;
25 s=(ll)s*s%mod,m>>=1;
26 }
27 return ans;
28 }
29 int calc(ll m){
30 m%=mod-1;
31 return (ll)pw[m%K]*PW[m/K]%mod;
32 }
33 int init(int m){
34 int n=1;
35 while (n1;
36 return n;
37 }
38 void ntt(int *a,int n,int p){
39 for(int i=0;i)
40 if (i<rev[i])swap(a[i],a[rev[i]]);
41 for(int i=2;i<=n;i<<=1){
42 int s=qpow(3,(mod-1)/i);
43 if (p)s=qpow(s,mod-2);
44 for(int j=0;ji)
45 for(int k=0,ss=1;k<(i>>1);k++,ss=(ll)ss*s%mod){
46 int x=a[j+k],y=(ll)a[j+k+(i>>1)]*ss%mod;
47 a[j+k]=(x+y)%mod,a[j+k+(i>>1)]=(x-y+mod)%mod;
48 }
49 }
50 if (p){
51 int s=qpow(n,mod-2);
52 for(int i=0;imod;
53 }
54 }
55 int main(){
56 read(),T=read(),scanf("%llu",&seed);
57 inv=qpow((mod+1>>1),K),pw[0]=PW[0]=1;
58 for(int i=1;i){
59 pw[i]=(ll)pw[i-1]*(mod+1>>1)%mod;
60 PW[i]=(ll)PW[i-1]*inv%mod;
61 }
62 while (T--){
63 n=read(),q=read(),x=read(),scanf("%lld",&k0);
64 for(int i=1;i<=n;i++)a[i]=read();
65 t=l=sum=ans=0,inv=qpow(n,mod-2);
66 while (n%(1<1)==0)t++;
67 for(int i=1;i<=n;i++)sum=(sum+a[i])%mod;
68 m=(n>>t+1)+1,sum=(ll)sum*inv%mod;
69 for(int i=0;i<=t;i++){
70 ans1[i]=a[x];
71 for(int j=1;j<=(n>>1);j++)b[j]=(a[j]+a[n-j+1])%mod;
72 for(int j=1;j<=n;j++)a[j]=b[j+1>>1];
73 }
74 x=(x-1>>t+1)+1;
75 for(int i=1;i<=m;i++)z[i]=a[(i-1<1)+1];
76 for(int i=1;i){
77 Z[i]=(z[i+1]-z[i]+mod)%mod,Z[(m<<1)-i-1]=(mod-Z[i])%mod;
78 g[i]=(mod+(i1))*inv%mod)%mod,g[i+m-1]=0;
79 f[i]=(i<<1),f[i+m-1]=(i<<1)-1;
80 }
81 memset(vis,0,sizeof(vis));
82 memset(ans2,0,sizeof(ans2));
83 for(int i=1;i<=(m-1<<1);i++)Ans[i].clear();
84 for(int i=1;i<=(m-1<<1);i++)
85 if (!vis[i]){
86 v.clear();
87 for(int j=i;!vis[j];j=f[j])vis[j]=1,v.push_back(j);
88 int l0=v.size(),n0=init(l0<<1);
89 l=max(l,l0),Ans[l0].resize(l0);
90 for(int j=0;j>1]>>1)+((j&1)*(n0>>1));
91 for(int j=0;j0;
92 for(int j=0;jg[v[j]];
93 ntt(a,n0,0),ntt(b,n0,0);
94 for(int j=0;jmod;
95 ntt(a,n0,1);
96 for(int j=0;jmod;
97 }
98 for(int i=1;i<=l;i++)
99 if (!Ans[i].empty()){
100 for(int j=0;jmod;
101 }
102 for(int i=1;i<=q;i++){
103 k=rd(seed)%k0;
104 if (k<=t)ans^=(ll)ans1[k]*calc(k)%mod*i;
105 else{
106 if (m==1)ans^=(ll)z[1]*calc(t+1)%mod*i;
107 else ans^=((ll)ans2[(k-t-1)%l]*calc(k)+sum)%mod*i;
108 }
109 }
110 printf("%lld\n",ans);
111 }
112 return 0;
113 }