我们发现我们可以直接让 $x_{i}=i$，然后模拟就行了.
code:
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#define N 500005
#define ll long long
#define setIO(s) freopen(s".in","r",stdin) ,freopen(s".out","w",stdout)
using namespace std;
const double pi=acos(-1);
char S[N];
struct cp
{
double x,y;
cp(double a=0,double b=0) { x=a,y=b; }
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); }
}A[N],B[N];
int mem[N*10],*ptr=mem;
void FFT(cp *a,int len,int flag)
{
int i,j,k,mid;
for(i=k=0;i<len;++i)
{
if(i>k) swap(a[i],a[k]);
for(j=len>>1;(k^=j)<j;j>>=1);
}
for(mid=1;mid<len;mid<<=1)
{
cp wn(cos(pi/mid), flag*sin(pi/mid)),x,y;
for(i=0;i<len;i+=mid<<1)
{
cp w(1,0);
for(j=0;j<mid;++j)
{
x=a[i+j],y=w*a[i+j+mid];
a[i+j]=x+y,a[i+j+mid]=x-y;
w=w*wn;
}
}
}
if(flag==-1)
{
for(i=0;i<len;++i) a[i].x/=(double)len;
}
}
struct num
{
int len;
int *a;
num(){}
num(int l) { len=l,a=ptr,ptr+=l; }
void fix(int l) { len=l,a=ptr,ptr+=l; }
void get_mod(int l) { len=l; }
num operator*(const num &b)
{
num c(len+b.len+1);
int lim=1,i,j,l=b.len;
while(lim<=c.len) lim<<=1;
for(i=0;i<lim;++i)
{
A[i].x=A[i].y=0;
B[i].x=B[i].y=0;
}
for(i=0;i<len;++i) A[i].x=a[i];
for(i=0;i<b.len;++i) B[i].x=b.a[i];
FFT(A,lim,1),FFT(B,lim,1);
for(i=0;i<lim;++i) A[i]=A[i]*B[i];
FFT(A,lim,-1);
for(i=0;i<c.len;++i) c.a[i]=(int)(A[i].x+0.5);
for(i=0;i<c.len-1;++i)
{
c.a[i+1]+=c.a[i]/10;
c.a[i]%=10;
}
for(i=c.len-1;i>=0;--i) if(c.a[i]) break;
c.get_mod(i+1);
return c;
}
num operator+(const num &b)
{
num c(max(len,b.len)+1);
int i,j;
for(i=0;i<b.len;++i) c.a[i]=b.a[i];
for(i=0;i<len;++i) c.a[i]+=a[i];
for(i=0;i<c.len-1;++i)
{
c.a[i+1]+=c.a[i]/10;
c.a[i]%=10;
}
for(i=c.len-1;i>=0;--i) if(c.a[i]) break;
c.get_mod(i+1);
return c;
}
num operator-(const num &b)
{
num c(len);
int i,j;
for(i=0;i<len;++i) c.a[i]=a[i];
for(i=0;i<b.len;++i) c.a[i]-=b.a[i];
for(i=0;i<c.len-1;++i)
{
if(c.a[i]<0)
{
c.a[i+1]-=(-c.a[i])/10+((-c.a[i])%10!=0);
c.a[i]=(c.a[i]%10+10)%10;
}
}
for(i=c.len-1;i>=0;--i) if(c.a[i]) break;
c.get_mod(i+1);
return c;
}
num operator/(const int b)
{
num c(len);
int i,j,re=0;
for(i=len-1;i>=0;--i)
{
re=re*10+a[i];
c.a[i]=re/b;
re%=b;
}
for(i=c.len-1;i>=0;--i)
{
if(c.a[i]) break;
}
c.get_mod(i+1);
return c;
}
void print() { for(int i=len-1;i>=0;--i) printf("%d",a[i]); }
void input()
{
scanf("%s",S);
int l=strlen(S);
fix(l);
for(int i=0;i<l;++i) a[i]=S[l-1-i]-'0';
}
void modify(int x)
{
int base=1,i,j;
for(i=0;base<=x;++i,base*=10);
fix(i);
for(j=0;j<i;++j) a[j]=x%10,x/=10;
}
};
int a[N],mul[N],dn[N];
void calc(int x,int *arr)
{
int i,j;
for(i=2;i<=x;++i)
{
if(x%i==0)
{
while(x%i==0) x/=i,arr[i]++;
}
}
if(x) arr[x]++;
}
int main()
{
// setIO("input");
int i,j,t,n,d,sum=0;
scanf("%d%d%d",&t,&n,&d);
for(i=1;i<=t;++i) scanf("%d",&a[i]),sum+=a[i];
for(i=1;i<=n;++i)
{
int x,y;
scanf("%d%d",&x,&y);
if(!a[y]) { printf("0/1\n"); return 0; }
calc(a[y],mul);
calc(sum,dn);
sum+=d;
a[y]+=d;
}
for(i=2;i<N;++i)
{
int tmp=min(mul[i],dn[i]);
mul[i]-=tmp;
dn[i]-=tmp;
}
num ans,det;
ans.modify(1);
for(i=2;i<N;++i)
{
det.modify(i);
for(j=1;j<=mul[i];++j) ans=ans*det;
}
ans.print();
printf("/");
ans.modify(1);
for(i=2;i<N;++i)
{
if(!dn[i]) continue;
det.modify(i);
for(j=1;j<=dn[i];++j) ans=ans*det;
}
ans.print();
return 0;
}
转播
