模拟一下发现答案与取球的顺序其实是无关的。
然后去膜拜题解发现的确这样。至于证明蒟蒻看不懂。
但是既然这样就是高精度模拟了?
双倍经验(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; }
果然是3越多越好、、滚回去学小学奥数算了、、、
然后就是高精度了、、比较脑残选择了手写、、更加脑残的选择了压位和快速幂、、然后跑的还行、、
代码越写越短了、、不过还有更短的比不过、、呵呵、、、
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; struct Hugeint{ ll len,num[10000]; Hugeint(){ len=1ll; memset(num,0,sizeof(num));} }An;ll n,two,thr,p[]={1,10,100,1000}; Hugeint Mul(Hugeint a,Hugeint b){ Hugeint c; c.len=a.len+b.len+1; for(ll i=1;i<=a.len;i++) for(ll j=1;j<=b.len;j++) c.num[i+j-1]+=a.num[i]*b.num[j]; for(ll 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; }Hugeint pow(ll b,ll 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; }inline int len(int x){ int r=0; while(x)r++,x/=10; return r; }void print(Hugeint a){ if(a.len<=25){ printf("%lld",a.num[a.len]); for(ll i=a.len-1;i;i--)printf("%04lld",a.num[i]); return;} printf("%lld",a.num[a.len]); for(ll i=a.len-1;i>=a.len-24;i--)printf("%04lld",a.num[i]); if(len(a.num[a.len])<4) printf("%lld\n",a.num[a.len-25]/p[len(a.num[a.len])]); }int main(){ scanf("%lld",&n); two=0,thr=n/3; if(n%3)two=2/(n%3),thr=(n-4/(n%3))/3; An=Mul(pow(2,two),pow(3,thr)); printf("%lld\n",(An.len-1<<2)+len(An.num[An.len])); print(An); return 0; }