2019 南昌网络赛 D. Interesting Series（生成函数 + 分治 + FFT）

首先式子化成： $F_n = \frac{1 - a^n}{1 - a}$
构建生成函数： $(x + a^{s_1}) * (x + a^{s_2}) * (x + a^{s_3}) * ... *(x + a^{s_n})$
(这个函数构建的灵感大概来自于：二项式定理？ $(a + b)^n$，然后要 k 个元素的集合，就是从 n 个集合中挑选k个，因此 $x^{n - k}$的系数恰好是 $\sum a^{sum}$, $sum$是 k 个元素的和，它相当于在个元素中选 k个元素出来)
然后仔细看这个生成函数，就是n个多项式相乘，可以用分治 + FFT。
这题模数是100003，可以用long double 跑FFT避免爆精度

代码：

#include<iostream>
using namespace std;
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define double long double
typedef long long ll;
const double pi = acos(-1.0);
const int maxn = 6e5 + 10;
const int mod = 100003;
struct complex{
	double r,i;
	complex(double _r = 0.0,double _i = 0.0) {
		r = _r;
		i = _i;
	}
	complex operator + (const complex & rhs) {
		return complex(rhs.r + r,rhs.i + i);
	}
	complex operator - (const complex & rhs) {
		return complex(r - rhs.r,i - rhs.i);
	}
	complex operator * (const complex & rhs) {
		return complex(r * rhs.r - i * rhs.i,r * rhs.i + i * rhs.r);
	}
};
complex A[maxn],B[maxn];
vector<int> g[maxn << 2];
int val[maxn],n,a,q;
int ifact[maxn],fact[maxn];
void change(complex a[],int len) {
	int tot = 0;
	while((1 << tot) < len) tot++;
	tot--;
	for(int i = 0; i < len; i++) {
		int cur = 0;
		for(int j = 0; j <= tot; j++)
			if(i & (1 << j))
				cur |= 1 << (tot - j);
		if(i < cur) swap(a[i],a[cur]);
	}
}
void fft(complex a[],int len,int type) {
	change(a,len);
	for(int i = 2; i <= len; i <<= 1) {
		complex wp = complex(cos(2 * pi * type / i),sin(2 * pi * type / i));
		for(int j = 0; j < len; j += i) {
			complex w = complex(1,0);
			for(int k = 0; k < i / 2; k++) {
				complex t = a[j + k];
				complex u = w * a[j + k + i / 2];
				a[j + k] = t + u;
				a[j + k + i / 2] = t - u;
				w = w * wp;
			}
		}
	}
	if(type == -1) {
		for(int i = 0; i < len; i++)
			a[i].r /= len;
	} 
}
void solve(int rt,int l,int r) {
	if(l == r) {
		g[rt].push_back(1);
		g[rt].push_back(val[l]);
		return ;
	}
	int mid = l + r >> 1;
	solve(rt << 1,l,mid);solve(rt << 1 | 1,mid + 1,r);
	int len = 1,tot = r - l + 1;
	while(len <= tot) len <<= 1;
	for(int i = 0; i < len; i++)
		A[i] = B[i] = complex(0,0);
	for(int i = 0; i <= mid - l + 1; i++)
		A[i] = complex(g[rt << 1][i],0);
	for(int i = 0; i <= r - mid; i++)
		B[i] = complex(g[rt << 1 | 1][i],0);
	fft(A,len,1);fft(B,len,1);
	for(int i = 0; i < len; i++)
		A[i] = A[i] * B[i];
	fft(A,len,-1);
	for(int i = 0; i < len; i++) {
		ll tmp = (ll)(A[i].r + 0.5);
		int z = tmp % mod;
		g[rt].push_back(z);
	}
	g[rt << 1].clear();g[rt << 1 | 1].clear();
}
int fpow(int a,int b) {
	int r = 1;
	while(b) {
		if(b & 1) r = 1ll * r * a % mod;
		b >>= 1;
		a = 1ll * a * a % mod;
	}
	return r;
}
int C(int x,int y) {
	if(y > x || y < 0) return 0;
	return 1ll * fact[x] * ifact[y] % mod * ifact[x - y] % mod;
}
int main() {
	fact[0] = 1;
	for(int i = 1; i < mod; i++)
		fact[i] = 1ll * fact[i - 1] * i % mod;
	ifact[mod - 1] = fpow(fact[mod - 1],mod - 2);
	for(int i = mod - 2; i >= 0; i--) {
		ifact[i] = 1ll * ifact[i + 1] * (i + 1) % mod;
	}
 	scanf("%d%d%d",&n,&a,&q);
	for(int i = 1; i <= n; i++) {
		scanf("%d",&val[i]);
		val[i] = fpow(a,val[i]); 
	}
	solve(1,1,n);
	int inv = fpow(a - 1,mod - 2);
	while(q--) {
		int x;
		scanf("%d",&x);
		int tmp = g[1][x];
		printf("%lld\n",1ll * (tmp - C(n,x) + mod) % mod * inv % mod);
	}
	return 0;
}