C++14(g++5.4) 解法, 执行用时: 1072ms, 内存消耗: 56528K, 提交时间: 2018-08-10 10:50:23
#include<bits/stdc++.h>
#define maxn 650050
#define Pi (3.1415926535897932)
#define ll long long
const int mod=200003;
using namespace std;
int A[maxn],B[maxn],n,m;
ll C[maxn];
struct cp
{
double x,y;
cp operator +(const cp &b){return (cp){x+b.x,y+b.y};}
cp operator -(const cp &b){return (cp){x-b.x,y-b.y};}
cp operator *(const cp &b){return (cp){x*b.x-y*b.y,x*b.y+y*b.x};}
cp operator *(const double &b){return (cp){x*b,y*b};}
}a[maxn],b[maxn],c[maxn],d[maxn],w[maxn];
int rev[maxn],s,t;
void prepare()
{
for(int i=0;i<s;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<t-1);
}
void dft(cp *a,int p)
{
for(int i=0;i<s;++i)if(i<rev[i])swap(a[i],a[rev[i]]);
w[0]=(cp){1,0};
for(int i=1,pi=2;i<s;i<<=1,pi<<=1)
{
cp wn=(cp){cos(Pi/i),sin(Pi/i)*p};
for(int j=i-2;j>=0;j-=2) w[j+1]=wn*(w[j]=w[j>>1]);
for(int j=0;j<s;j+=pi)
{
cp *l=a+j,*r=a+j+i;
for(int k=0;k<i;++k)
{
cp tmp=r[k]*w[k];
r[k]=l[k]-tmp;
l[k]=l[k]+tmp;
}
}
}
if(p==-1)
for(int i=0;i<s;++i)
a[i].x/=s,a[i].y/=s;
}
void fft(int *A,int *B,ll *C,int n,int m)
{
for(int i=0;i<n;++i) a[i]=(cp){(double)(A[i]&32767),(double)(A[i]>>15)};
for(int i=0;i<m;++i) b[i]=(cp){(double)(B[i]&32767),(double)(B[i]>>15)};
for(s=1,t=0;s<n+m;s<<=1,t++);
for(int i=n;i<s;++i) a[i]=(cp){0,0};
for(int i=m;i<s;++i) b[i]=(cp){0,0};
prepare();
dft(a,1); dft(b,1);
for(int i=0;i<s;++i)
{
int j=(s-1)&(s-i);
c[j]=(cp){a[i].x+a[j].x,a[i].y-a[j].y}*0.5*b[i];
d[j]=(cp){a[i].y+a[j].y,a[j].x-a[i].x}*0.5*b[i];
}
dft(c,1); dft(d,1);
for(int i=0;i<s;++i)
{
ll u=c[i].x/s+0.5,v=c[i].y/s+0.5;
ll x=d[i].x/s+0.5,y=d[i].y/s+0.5;
C[i]=(u+(v+(x%mod)<<15)%mod+((y%mod)<<30))%mod;
}
}
int aa[maxn],p,q;
ll f[maxn];
ll pw22[maxn],inv_pw22[maxn];
ll fac[maxn],inv_fac[maxn],inv[maxn],pwq[maxn],pwp[maxn];
ll qpow(ll a,ll m)
{
m%=(mod-1);
ll ret=1;
while(m>0)
{
if(m&1) ret=ret*a%mod;
a=a*a%mod;
m>>=1;
}
return ret;
}
int main()
{
fac[0]=fac[1]=inv[0]=inv[1]=inv_fac[0]=inv_fac[1]=1;
for(int i=2;i<=100000;++i)
{
fac[i]=fac[i-1]*i%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
inv_fac[i]=inv_fac[i-1]*inv[i]%mod;
}
for(int i=0;i<=100000;++i)
{
pw22[i]=qpow(2,(ll)i*i);
inv_pw22[i]=qpow(pw22[i],mod-2);
}
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&p,&q);
pwq[0]=1; pwq[1]=q;
pwp[0]=1; pwp[1]=p;
for(int i=2;i<=n;++i) pwq[i]=pwq[i-1]*q%mod;
for(int i=2;i<=n;++i) pwp[i]=pwp[i-1]*p%mod;
for(int i=0;i<n;++i) scanf("%d",&aa[i]);
for(int i=0;i<n;++i) A[i]=aa[n-1-i]*fac[n-1-i]%mod;
for(int i=0;i<n;++i) B[i]=pwq[i]*inv_fac[i]%mod;
fft(A,B,C,n,n);
for(int i=0;i<n;++i) f[n-i-1]=C[i];
for(int i=0;i<n;++i) A[i]=pwp[i]*f[i]%mod*pw22[i]%mod*inv_fac[i]%mod;
int pla=0;
for(int i=-(n-1);i<n;++i) B[pla++]=inv_pw22[i>=0?i:-i];
//printf("pla=%d\n",pla);
//for(int i=0;i<pla;++i) printf("B[%d]=%d\n",i,(int)B[i]);
fft(A,B,C,n,pla);
for(int i=0;i<n;++i) C[n-1+i]=C[n-1+i]*pw22[i]%mod;
for(int i=0;i<n;++i) printf("%d%c",(int)C[n-1+i],i==n-1?'\n':' ');
}
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 1864ms, 内存消耗: 50956K, 提交时间: 2018-10-07 21:50:46
#include <bits/stdc++.h>
using namespace std;
// double 精度对$10^9+7$ 取模最多可以做到$2^{20}$
const int MOD = 2e5+3;
const double PI = acos(-1);
typedef complex<double> Complex;
typedef long long ll;
const int N = 1<<19, L = 15, MASK = (1 << L) - 1;
Complex w[N];
void FFTInit() {
for (int i = 0; i < N; ++i) {
w[i] = Complex(cos(2 * i * PI / N), sin(2 * i * PI / N));
}
}
void FFT(Complex p[], int n) {
for (int i = 1, j = 0; i < n - 1; ++i) {
for (int s = n; j ^= s >>= 1, ~j & s;);
if (i < j) {
swap(p[i], p[j]);
}
}
for (int d = 0; (1 << d) < n; ++d) {
int m = 1 << d, m2 = m * 2, rm = n >> (d + 1);
for (int i = 0; i < n; i += m2) {
for (int j = 0; j < m; ++j) {
Complex &p1 = p[i + j + m], &p2 = p[i + j];
Complex t = w[rm * j] * p1;
p1 = p2 - t;
p2 = p2 + t;
}
}
}
}
Complex A[N], B[N], C[N], D[N];
void mul(int a[N], int b[N]) {
for (int i = 0; i < N; ++i) {
A[i] = Complex(a[i] >> L, a[i] & MASK);
B[i] = Complex(b[i] >> L, b[i] & MASK);
}
FFT(A, N), FFT(B, N);
for (int i = 0; i < N; ++i) {
int j = (N - i) % N;
Complex da = (A[i] - conj(A[j])) * Complex(0, -0.5),
db = (A[i] + conj(A[j])) * Complex(0.5, 0),
dc = (B[i] - conj(B[j])) * Complex(0, -0.5),
dd = (B[i] + conj(B[j])) * Complex(0.5, 0);
C[j] = da * dd + da * dc * Complex(0, 1);
D[j] = db * dd + db * dc * Complex(0, 1);
}
FFT(C, N), FFT(D, N);
for (int i = 0; i < N; ++i) {
long long da = (long long)(C[i].imag() / N + 0.5) % MOD,
db = (long long)(C[i].real() / N + 0.5) % MOD,
dc = (long long)(D[i].imag() / N + 0.5) % MOD,
dd = (long long)(D[i].real() / N + 0.5) % MOD;
a[i] = ((dd << (L * 2)) + ((db + dc) << L) + da) % MOD;
}
}
int power(int x,ll p){
int ans=1;
int base=x;
while(p){
if(p&1){
ans=1ll*ans*base%MOD;
}
p>>=1;
base=1ll*base*base%MOD;
}
return ans;
}
int inv(int x){
return power(x,MOD-2);
}
int u[N],v[N];
int a[N],b,c,d,n;
int fac[N],dpw[N],bpw[N],cpw[N];
int res[N];
int main(){
FFTInit();
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&b,&d);
c=2;
for(int i=0;i<n;i++)scanf("%d",&a[i]);
fac[0]=dpw[0]=bpw[0]=cpw[0]=1;
for(int i=1;i<n;i++){
fac[i]=1ll*fac[i-1]*i%MOD;
dpw[i]=1ll*dpw[i-1]*d%MOD;
bpw[i]=1ll*bpw[i-1]*b%MOD;
cpw[i]=power(c,1ll*i*i);
}
memset(u,0,sizeof(u));
memset(v,0,sizeof(v));
for(int i=0;i<n;i++){
u[i]=a[i];
u[i]=1ll*u[i]*dpw[i]%MOD;
u[i]=1ll*u[i]*fac[i]%MOD;
v[i]=inv(fac[n-1-i]);
}
mul(u,v);
for(int i=0;i<n;i++){
res[i]=u[n-1+i];
// printf("%lld\n",res[i]);
}
memset(u,0,sizeof(u));
memset(v,0,sizeof(v));
for(int i=0;i<n;i++){
u[i]=bpw[i];
u[i]=1ll*u[i]*res[i]%MOD;
u[i]=1ll*u[i]*cpw[i]%MOD;
u[i]=1ll*u[i]*inv(dpw[i])%MOD;
u[i]=1ll*u[i]*inv(fac[i])%MOD;
v[n+i]=v[n-i]=inv(cpw[i]);
}
mul(u,v);
for(int i=0;i<n;i++){
printf("%lld%c",1ll*u[n+i]*cpw[i]%MOD,i==n-1?'\n':' ');
}
}
}
%5Ej))%5C%20mod%5C%20200003%20%5C%5D)