BZOJ1498: [NOI2006]神奇的口袋【高精度】

dzy posted @ 2013年6月12日 12:56 in BZOJ with tags BZOJ NOI 高精度 , 2453 阅读

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

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

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

双倍经验(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;
}
Avatar_small
networkslog.com 说:
2023年6月09日 13:59

We discuss, review, write and explain about different products, services, technology and more through our website which are for learning and educational purposes only. That being said, though we try to be up to networkslog.com date with the information, there sometimes or more can be information being outdated and any issues or problems that arise from the use of the information present on our website is solely on the users only as we try to provide this website for free in good faith only.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter