求 $k=1,2,\cdots,n \space \space \sum\limits_{i=1}^n a_i^k$
$n \leq 2 \times 10^5$
sol：
时隔多年终于卡过去了
之前 $O(nlog^2n) + O(nlogn)$ 卡了我的 $O(nlog^2n) + O(nlog^2n)$ ，有点自闭
然后 fread + 编译优化 + 预处理单位根 + 不在 fft 里计算 rev 数组大力卡进时限
#include <bits/stdc++.h>
#define LL long long
#define rep(i, s, t) for (register int i = (s), i##end = (t); i <= i##end; ++i)
#define dwn(i, s, t) for (register int i = (s), i##end = (t); i >= i##end; --i)
using namespace std;
const int Size=<<;
char buffer[Size],*head,*tail;
inline char Getchar() {
if(head==tail) {
int l=fread(buffer,,Size,stdin);
tail=(head=buffer)+l;
}
if(head==tail) return -;
return *head++;
}
inline int read() {
int x=,f=;char c=Getchar();
for(;!isdigit(c);c=Getchar()) if(c=='-') f=-;
for(;isdigit(c);c=Getchar()) x=x*+c-'';
return x*f;
}
const int mod = , maxn = ;
int a[maxn], r[maxn], lg[maxn], n, k;
inline int skr(int x, int t) {
int res = ;
while (t) {
if (t & )
res = 1LL * res * x % mod;
x = 1LL * x * x % mod;
t = t >> ;
}
return res;
}
int wn[maxn], iwn[maxn];
void init(int n) {
wn[] = iwn[] = ;
rep(i, , n-) wn[i] = skr(, (mod - ) / (i << ));
rep(i, , n-) iwn[i] = skr(, (mod - ) / (i << ));
}
inline void fft_init(int n) {rep(i, , n - ) r[i] = (r[i >> ] >> ) | ((i & ) << (lg[n] - ));}
inline void fft(int *a, int n, int type) {
rep(i, , n - ) if (i < r[i]) swap(a[i], a[r[i]]);
for (int i = ; i < n; i <<= ) {
//int wn = skr(3, (mod - 1) / (i << 1));
//if (type == -1)
// wn = skr(wn, mod - 2);
int twn = (type == -) ? iwn[i] : wn[i];
for (int j = ; j < n; j += (i << )) {
int w = ;
for (int k = ; k < i; k++, w = 1LL * w * twn % mod) {
int x = a[j + k], y = 1LL * w * a[j + k + i] % mod;
a[j + k] = (x + y) % mod;
a[j + k + i] = (x - y + mod) % mod;
}
}
}
if (type == -) {
int inv_n = skr(n, mod - );
rep(i, , n - ) a[i] = 1LL * a[i] * inv_n % mod;
}
}
int A[maxn], B[maxn];
int C[maxn], D[maxn];
int mul(int *A, int *B, int len) {
fft_init(len);
// fft_init(len);
fft(A, len, );
// for(int i=0;i<len;i++)cout<<A[i]<<" ";
// cout<<endl;
fft(B, len, );
for (int i = ; i < len; i++) A[i] = (LL)A[i] * B[i] % mod;
fft(A, len, -);
--len;
while (!A[len]) --len;
return len;
}
vector<int> poly[maxn];
int solve(int l, int r) {
if (l == r)
return poly[l].size() - ;
int mid = (l + r) >> ;
int ls = solve(l, mid), rs = solve(mid + , r);
int L = ;
for (; L <= ls + rs; L <<= )
; for (int i = ; i <= ls; i++) A[i] = poly[l][i];
for (int i = ls + ; i < L; i++) A[i] = ; for (int i = ; i <= rs; i++) B[i] = poly[mid + ][i];
for (int i = rs + ; i < L; i++) B[i] = ;
poly[l].clear();
poly[mid + ].clear(); L = mul(A, B, L);
for (int i = ; i <= L; i++) poly[l].push_back(A[i]);
return L;
}
int g[maxn], f[maxn];
void mulfac(int *A, int *B, int len) {
fft_init(len);
fft(A, len, );
fft(B, len, );
for (int i = ; i < len; i++) A[i] = 1LL * A[i] * B[i] % mod;
fft(A, len, -);
}
void cdq_fft(int *f, int *g, int l, int r) {
if (l == r) {
(f[l] += (1LL * l * g[l] % mod)) %= mod;
return;
}
int mid = (l + r) >> ;
cdq_fft(f, g, l, mid);
int len = , ls = , rs = ;
// for(;len <= ((r - l + mid)<<1);len <<= 1);
// for(int i=0;i<len;i++)A[i] = B[i] = 0;
for (int i = l; i <= mid; i++) C[ls++] = f[i];
for (int i = ; i <= r - l; i++) D[rs++] = g[i];
for (; len <= (ls + rs - ); len <<= )
;
mulfac(C, D, len);
for (int i = mid + ; i <= r; i++) f[i] = (f[i] + C[i - l - ]) % mod;
for (int i = ; i < len; i++) C[i] = D[i] = ;
cdq_fft(f, g, mid + , r);
}
int main() {
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
lg[] = -; init( << );
rep(i, , maxn - ) lg[i] = lg[i >> ] + ;
int T = read();
while (T--) {
int ans = ;
n = read();
for (int i = ; i <= n; i++) {
a[i] = read();
if(a[i] >= mod) a[i] -= mod;
poly[i].push_back();
poly[i].push_back(a[i]);
}
solve(, n);
for (int i = ; i < poly[].size(); i++) g[i] = (((i & ) ? : (-)) * poly[][i] + mod) % mod;
poly[].clear();
cdq_fft(f, g, , n);
for (int i = ; i <= n; i++) ans ^= f[i];
memset(f, , sizeof(f));
memset(g, , sizeof(g));
memset(A, , sizeof(A));
memset(B, , sizeof(B));
memset(C, , sizeof(C));
memset(D, , sizeof(D));
cout << ans << endl;
}
}
然而这种 shabi 题为什么我能写 6K，给镘写也就 100 行，我菜的真实