ZeroJudge i112 - 三則運算 解題心得( 題目 )
解題概念:大數、NTT
解題方法:
Java參考程式碼(有更好意見可留言於下方，謝謝!):
//Author:En Chi Tsung(欉恩祁)
//Date:2022/05/16
import java.io.*;
import java.math.*;
public class zji212 {
public static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
public static BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
public static int ret,rd;
public static long floor;
public static int G=3;
public static int N=1<<21,P=(479<<21)+1,PP=21;
public static void main(String[] args) throws Exception{
String[] in=br.readLine().split(" ");
long[] a=new long[N];
long[] b=new long[N];
long[] c=new long[N];
final String F=in[0];
final String S=in[2];
final String O=in[1];
if(O.equals("+")) {
for(int i=F.length()-1,j=0;i>=0;i--,j++) {
a[j]=F.charAt(i)-'0';
}
for(int i=S.length()-1,j=0;i>=0;i--,j++) {
b[j]=S.charAt(i)-'0';
}
final int len=Math.max(F.length(),S.length())+5;
for(int i=0;i<len;i++) {
c[i]=a[i]+b[i];
if(c[i]>=10) {
a[i+1]++;
c[i]-=10;
}
}
int idx;
for(idx=len;idx>0;idx--) {
if(c[idx]!=0)break;
}
for(;idx>=0;idx--) {
bw.write(c[idx]+"");
}
bw.flush();
}
else if(O.equals("-")){
for(int i=F.length()-1,j=0;i>=0;i--,j++) {
a[j]=F.charAt(i)-'0';
}
for(int i=S.length()-1,j=0;i>=0;i--,j++) {
b[j]=S.charAt(i)-'0';
}
long dl;
final int len=F.length();
for(int i=0;i<len;i++) {
dl=a[i]-b[i];
if(dl<0) {
a[i+1]--;
c[i]=(dl+10)%10;
}
else {
c[i]=dl;
}
}
int idx;
for(idx=len;idx>0;idx--) {
if(c[idx]!=0)break;
}
for(;idx>=0;idx--) {
bw.write(c[idx]+"");
}
bw.flush();
}
else {
for(int i=F.length()-1,j=0;i>=0;i--,j++) {
a[j]=F.charAt(i)-'0';
}
for(int i=S.length()-1,j=0;i>=0;i--,j++) {
b[j]=S.charAt(i)-'0';
}
if(F.length()+S.length()<=60000) {
N=1<<16;
PP=16;
P=998244353;
}
final long e=fast(N,P-2);
NTT(a,1,N,PP,P);
NTT(b,1,N,PP,P);
for(int i=0;i<N;i++) {
c[i]=(a[i]*b[i])%P;
}
NTT(c,-1,N,PP,P);
for(int i=0;i<N;i++) {
c[i]=(c[i]*e)%P;
}
for(int i=0;i<N-1;i++) {
c[i+1]+=c[i]/10;
c[i]%=10;
}
int idx;
for(idx=N-1;idx>0;idx--) {
if(c[idx]!=0)break;
}
for(;idx>=0;idx--) {
bw.write(c[idx]+"");
}
bw.write("\n");
bw.flush();
}
}
public static void NTT(long[] in,int inv,final int N,final int PP,final int P) {
long o;
int u,y;
long x,w,f;
for(int i=0;i<N;i++) {
u=0;
for(int j=0;j<PP;j++) {
y=(1<<j);
if((y&i)==y) {
u|=(1<<(PP-1-j));
}
}
if(i<u) {
o=in[i];//swap
in[i]=in[u];
in[u]=o;
}
}
for(int k=1;k<N;k<<=1){
w=fast(G,(long)(P-1)/(k<<1)*(P-1+inv));
for(int j=0;j<N;j+=k<<1){
x=1;
for(int i=j;i<j+k;i++,x=x*w% P){
f=x*in[i+k]%P;
in[i+k]=(in[i]-f+P)%P;
in[i]=(in[i]+f)%P;
}
}
}
}
public static long fast(long x,long pw) {
if(pw==0)return 1;
if(pw==1) {
return x;
}
else {
long h=fast(x,pw>>1);
if((pw&1)==0) {
return h*h%P;
}
else {
return h*h%P*x%P;
}
}
}
}
文章標籤
全站熱搜
