提交记录 5117


用户 题目 状态 得分 用时 内存 语言 代码长度
Komachi 1004a. 【模板题】高精度乘法2 Accepted 100 2.275 ms 284 KB C++ 2.28 KB
提交时间 评测时间
2018-08-06 22:29:24 2020-08-01 00:11:11
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
  
#define Death Komachi
#define REP(i,a,b) for(int i=(a),i##_end_=(b);i<i##_end_;i++)
#define DREP(i,a,b) for(int i=(a),i##_end_=(b);i>i##_end_;i--)
#define M 160000
#define Mod 998244353
#define Base 100
  
bool F;
int Rev[M];
int A[M],B[M],w[M],a,b,n,m;
char S[M];

#define ULL unsigned long long
#define LLL __uint128_t
namespace FastMod{
	ULL x;
	int s;
	void Init(int n){
		s=log2(n-1);
		x=(( LLL(1) << (s + 64)) +n-1)/n;
	}
	inline int Div(ULL a){
		return a-((LLL(a)*x>>s)>>64)*Mod;
	}
};

void Clear(){
    REP(i,0,n)A[i]=B[i]=0;
}
void Get(char *S,int *A,int &l){
    if(S[0]=='-')F^=1;
    int pow=1;
    DREP(i,strlen(S)-1,-1)if(S[i]!='-'){
        A[l]+=pow*(S[i]&15),pow*=10;
        if(pow==Base)pow=1,l++;
    }
    l++;
}
void Rever(){
    REP(i,0,n)
        Rev[i]=(Rev[i>>1]>>1)|((i&1)<<m-1);
}
  
int Pow(int k,int p){
    int Res=1;
    for(;p;p>>=1,k=FastMod::Div((ULL)k*k))if(p&1)Res=FastMod::Div((ULL)Res*k);
    return Res;
}
void DFT(int *A,int p){
    REP(i,0,n)if(i<Rev[i])swap(A[i],A[Rev[i]]);
    
	w[0]=1;
	for(int i=1,pi=2;i<n;i<<=1,pi<<=1){
		int wn=Pow(3,(Mod-1)/pi);
        if(p)wn=Pow(wn,Mod-2);
		for(int j=i-2;j>=0;j-=2)w[j+1]=FastMod::Div((ULL)wn*(w[j]=w[j>>1]));
		for(int j=0;j<n;j+=pi){
			int *l=A+j,*r=A+j+i;
			REP(k,0,i){
				int Tmp=FastMod::Div((ULL)r[k]*w[k]);
				r[k]=l[k]-Tmp;
				r[k]<0?r[k]+=Mod:0;
				l[k]=l[k]+Tmp;
				l[k]>=Mod?l[k]-=Mod:0;
			}
		}
	}
    if(p){
        int Inv=Pow(n,Mod-2);
        REP(i,0,n)A[i]=FastMod::Div((ULL)A[i]*Inv);
    }
}
  
int main(){
	FastMod::Init(Mod);
//	printf("%d\n",FastMod::Div(2333333ull*2333333));
//	printf("%d\n",2333333ull*2333333%Mod);
    while(scanf("%s",S)!=EOF){
        Clear();
        F=a=b=0;
          
        Get(S,A,a);
        scanf("%s",S);
        Get(S,B,b);
          
        for(n=1,m=0;n<a+b;n<<=1,m++);
        Rever();
        DFT(A,0);
        DFT(B,0);
        REP(i,0,n)A[i]=FastMod::Div((ULL)A[i]*B[i]);
        DFT(A,1);
          
        REP(i,0,n){
            A[i+1]+=A[i]/Base;
            A[i]%=Base;
        }
        
        if(F)putchar('-');
        int i=n;
        while(i>0 && !A[i])i--;
        printf("%d",A[i--]);
        while(i>=0)printf("%02d",A[i--]);
        puts("");
    }
    return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #12.275 ms284 KBAcceptedScore: 100


Judge Duck Online | 评测鸭在线
Server Time: 2024-03-29 00:21:08 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用