DZY 's BLOG

模拟一下发现答案与取球的顺序其实是无关的。

然后去膜拜题解发现的确这样。至于证明蒟蒻看不懂。

但是既然这样就是高精度模拟了？

双倍经验（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;
}