模拟一下发现答案与取球的顺序其实是无关的。
然后去膜拜题解发现的确这样。至于证明蒟蒻看不懂。
但是既然这样就是高精度模拟了?
双倍经验(1416 && 1498)
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; struct Hugeint{int len,num[10000]; Hugeint(){ len=1; memset(num,0,sizeof(num));}}An1,An2; int num[1005],A[10000]={0},B[10000]={0},flag[20005]={0},prime[10000],cnt=0,sum=0; inline int pre(int n){ for(int i=2;i<=n;i++){ if(!flag[i]) prime[cnt++]=i; for(int j=0;j<cnt&&prime[j]*i<=n;j++){ flag[i*prime[j]]=1; if(i%prime[j]==0)break; } } }inline Hugeint Mul(Hugeint a,Hugeint b){ Hugeint c; c.len=a.len+b.len+1; for(int i=1;i<=a.len;i++) for(int j=1;j<=b.len;j++) c.num[i+j-1]+=a.num[i]*b.num[j]; for(int i=1;i<c.len;i++) if(c.num[i]>9999) c.num[i+1]+=c.num[i]/10000,c.num[i]%=10000; while(c.num[c.len]>9999) c.len++,c.num[c.len]+=c.num[c.len-1]/10000,c.num[c.len-1]%=10000; while(c.num[c.len]==0&&c.len>1) c.len--; return c; }inline Hugeint pow(int b,int p){ Hugeint ans,bb; ans.len=bb.len=ans.num[1]=1ll; bb.num[1]=b; while(p){if(p&1ll)ans=Mul(ans,bb);p>>=1ll;bb=Mul(bb,bb);} return ans; }void print(Hugeint a){ printf("%d",a.num[a.len]); for(int i=a.len-1;i;i--)printf("%04d",a.num[i]); }inline void pushA(int k){ for(int i=0;k>1&&i<cnt&&prime[i]<=k;i++) while(k%prime[i]==0)A[i]++,k/=prime[i]; }inline void pushB(int k){ for(int i=0;k>1&&i<cnt&&prime[i]<=k;i++) while(k%prime[i]==0)B[i]++,k/=prime[i]; }int main(){ int n,m,d,x,y; pre(20000); scanf("%d%d%d",&n,&m,&d); for(int i=1;i<=n;i++)scanf("%d",&num[i]),sum+=num[i]; for(int i=1;i<=m;i++){ scanf("%d%d",&x,&y); if(num[y]==0){ printf("0/1\n");return 0;} pushA(num[y]); pushB(sum); num[y]+=d; sum+=d; }for(int i=0;i<cnt;i++) if(A[i]&&B[i]){ if(A[i]>B[i]) A[i]-=B[i], B[i]=0; else B[i]-=A[i], A[i]=0; }An1.num[1]=An2.num[1]=1; for(int i=0;i<cnt;i++) if(A[i]) An1=Mul(An1,pow(prime[i],A[i])); for(int i=0;i<cnt;i++) if(B[i]) An2=Mul(An2,pow(prime[i],B[i])); print(An1);putchar('/');print(An2);putchar('\n');return 0; }