关于此题的hack
查看原帖
关于此题的hack
348716
封禁用户楼主2020/5/26 20:47
#include<bits/stdc++.h>
#define n 131072
using namespace std;
struct apple
{
	double a,b;
	apple(double a=0,double b=0):a(a),b(b){}
	void operator+=(apple other)
	{
		a+=other.a;
		b+=other.b;
	}
	void operator-=(apple other)
	{
		a-=other.a;
		b-=other.b;
	}
	void operator*=(apple other)
	{
		double aa=a*other.a-b*other.b,bb=a*other.b+b*other.a;
		a=aa,b=bb;
	}
}ans[n],ans2[n],ans3[n],d1[n],d2[n],d[n],dd[n],f1[n],f2[n],cj[n+1];
char s1[n],s2[n];
int ff[n];
double pi=2*acos(-1);
void fft(apple d[],int nn,int cz,int cs)
{
apple cs2;
	if(nn==1)
	{
		ans[cs]=d[cs];
		return;
	}
	int bb=nn>>1;
	for(int i=0;i<bb;i++)dd[cs+i]=d[cs+(i<<1)];
	for(int i=0;i<bb;i++)dd[cs+bb+i]=d[cs+(i<<1|1)];
	for(int i=cs;i<cs+nn;i++)d[i]=dd[i];
	fft(d,bb,cz,cs);
	fft(d,bb,cz,cs+bb);
	for(int i=0;i<bb;i++)
	{
		cs2=cj[n/nn*i];
		apple ccs=cs2;
		if(cz==-1)
		{
			cs2.a=ccs.a/(ccs.a*ccs.a+ccs.b*ccs.b);
			cs2.b=-ccs.b/(ccs.a*ccs.a+ccs.b*ccs.b);
		}
		cs2*=ans[cs+bb+i];
		ans3[cs+i]=ans[cs+i];
		ans3[cs+i]+=cs2;
	}
	for(int i=bb;i<nn;i++)
	{
		cs2=cj[n/nn*i];
		apple ccs=cs2;
		if(cz==-1)
		{
			cs2.a=ccs.a/(ccs.a*ccs.a+ccs.b*ccs.b);
			cs2.b=-ccs.b/(ccs.a*ccs.a+ccs.b*ccs.b);
		}
		cs2*=ans[cs+i];
		ans3[cs+i]=ans[cs+i-bb];
		ans3[cs+i]+=cs2;
	}
	for(int i=cs;i<cs+nn;i++)ans[i]=ans3[i];
}
int main()
{
	cj[0]=apple(1,0),cj[1]=apple(cos(pi/n),sin(pi/n));
	for(int i=2;i<=n;i++)cj[i]=cj[i-1],cj[i]*=cj[1];
	int pppp;
	cin>>pppp;
	scanf("%s%s",s1,s2);
	int l1=strlen(s1),l2=strlen(s2);
	for(int i=0;i<l1;i++)f1[l1-i-1].a=s1[i]-'0';
	for(int i=0;i<l2;i++)f2[l2-i-1].a=s2[i]-'0';
	fft(f1,n,1,0);
	for(int i=0;i<n;i++)d1[i]=ans[i];
	fft(f2,n,1,0);
	for(int i=0;i<n;i++)d2[i]=ans[i];
	for(int i=0;i<n;i++)d1[i]*=d2[i],d[i]=d1[i];
	fft(d,n,-1,0);
	for(int i=0;i<n;i++)ff[i]=(ans[i].a+0.5)/n;
	for(int i=0;i<n;i++)ff[i+1]+=ff[i]/10,ff[i]%=10;
	int aa=0;
	for(int i=n-1;i>=0;i--)if(ff[i])
	{
		aa=i;
		break;
	}
	for(int i=aa;i>=0;i--)printf("%d",ff[i]);
	return 0;
}

这份代码在 darkbzoj 上WA了(bzoj2179),但在你谷上A了,能hack一下吗?

2020/5/26 20:47
加载中...