求条
查看原帖
求条
1371790
ljh0727楼主2025/2/5 20:42

wa 了,哪错了???

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

#define MAX(x) (1<<(x))

const int N=1e5+5;
const double PI=acos(-1.0);

string s1,s2;

double ax[N],ay[N],bx[N],by[N];
int n1[N],n2[N],n3[N];

int kkc1[15]={0,8,1,4,72,73,4,78,73,2,81,52};
int kkc2[15]={0,9,101,72,4,3,11,1,3,75,6,4};

int f1(int x,int bits){
    int ret=0;
    for(int i=0;i<bits;i++){
        ret<<=1;
        ret|=x&1;
        x>>=1;
    }
    return ret;
}

void f2(double *a,double *b,int n,bool rev){
    int bits=0;
    while(1<<bits<n) 
		bits++;
    for(int i=0;i<n;i++){
        int j=f1(i, bits);
        if (i<j){
            swap(a[i],a[j]);
            swap(b[i],b[j]);
        }
    }
    for (int len=2;len<=n;len<<=1){
        int half=len >> 1;
        double wmx=cos(2*PI/len),wmy=sin(2*PI/len);
        if(rev) 
			wmy=-wmy;
        for(int i=0;i<n;i+=len){
            double wx=1,wy=0;
            for(int j=0;j<half;j++){
                double cx=a[i+j],cy=b[i+j];
                double dx=a[i+j+half],dy=b[i+j+half];
                double ex=dx*wx-dy*wy,ey=dx*wy+dy*wx;
                a[i+j]=cx+ex,b[i+j]=cy+ey;
                a[i+j+half]=cx-ex,b[i+j+half]=cy-ey;
                double wnx=wx*wmx-wy*wmy,wny=wx*wmy+wy* wmx;
                wx=wnx,wy=wny;
            }
        }
    }
    if(rev){
    	for(int i=0;i<n;i++){
        	a[i]/=n;b[i]/=n;
		}
	}
}

int f3(int l1,int l2,int ans[]){
    int len=max(l1,l2),ln;
    for(ln=0;MAX(ln)<len;++ln);
    len=MAX(++ln);
    for(int i=0;i<len;i++){
        if(i>=l1)ax[i]=0,ay[i]=0;
        else ax[i]=n1[i],ay[i]=0;
    }
    f2(ax,ay,len,false);
    for(int i=0;i<len;i++){
        if(i>=l2)bx[i]=0,by[i]=0;
        else bx[i]=n2[i],by[i]=0;
    }
    f2(bx,by,len,false);
    for(int i=0;i<len;i++){
        double cx=ax[i]*bx[i]-ay[i]*by[i];
        double cy=ax[i]*by[i]+ay[i]*bx[i];
        ax[i]=cx,ay[i]=cy;
    }
    f2(ax,ay,len,true);
    for(int i=0;i<len;i++)
        ans[i]=(int)(ax[i]+0.5);
    return len;
}

void f4(){
    int l;
    string ans;
    memset(n3,0,sizeof(n3));
    int l1=(int)s1.size();
    int l2=(int)s2.size();
    for(int i=0;i<l1;i++)
        n1[i]=s1[l1-i-1]-'0';
    for(int i=0;i<l2;i++)
        n2[i]=s2[l2-i-1]-'0';
    l=f3(l1,l2,n3);
    int x;
    for(int i=0;i<l||n3[i]>=10;i++){
        n3[i+1]+=n3[i]/10;
        n3[i]%=10;
        x=i;
    }
    l=x;
    while(n3[l]<=0&&l>0)
		l--;
	int kc=0;
   	for(int i=l;i>=0;i--){
   		kc=kc*10+n3[i];
	}
	printf("%c",(char)kc);
}

int main(){
	for(int i=1;i<=11;i++){
		s1="";s2="";
		while(kkc1[i]){
			s1+=(char)(kkc1[i]%10+'0');
			kkc1[i]/=10;
		}
		while(kkc2[i]){
			s2+=(char)(kkc2[i]%10+'0');
			kkc2[i]/=10;
		}
		f4();
		
	}
    return 0;
}

2025/2/5 20:42
加载中...