记录编号	380016	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[Keller战纪·正传·妖姬篇][HZOI 2015]Keller 异或 凤凰神	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	0.331 s
提交时间	2017-03-08 07:42:38	内存使用	9.74 MiB

#include <stdio.h>
#include <ctime>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <cmath>
#include <iostream>
#define RG register
#define IL inline
#define Mem(a,v) memset(a,v,sizeof a)
#define Mcpy(a,b) memcpy(a,b,sizeof a)
using namespace std;
typedef long long LL;
const int maxn = (1<<18)+10;
const double Pi = acos(-1);
struct Complex
{
	double x, y;
	Complex(double x=0.0,double y=0.0): x(x), y(y){}
	Complex operator + (const Complex &b){ return Complex(x+b.x,y+b.y); }
	Complex operator - (const Complex &b){ return Complex(x-b.x,y-b.y); }
	Complex operator * (const Complex &b){ return Complex(x*b.x-y*b.y,x*b.y+y*b.x); }
	Complex operator * (const double &b){ return Complex(x*b, y*b); }
};
Complex a[maxn],b[maxn];
int rev[maxn];
IL void FFT(Complex *a,int n,int type){
	RG int i,j,k; Complex wn,w;
	for(i=1; i<n; i++) if(i>rev[i]) swap(a[i], a[rev[i]]);
	for(k=2; k<=n; k<<=1){
		for(wn=Complex(cos(2.0*Pi*type/k),sin(2.0*Pi*type/k)),j=0; j<n; j+=k){
			for(w=Complex(1),i=0; i<(k>>1); i++, w=w*wn){
				Complex t1=a[i+j], t2=a[i+j+(k>>1)];
				a[i+j]=t1+w*t2;
				a[i+j+(k>>1)]=t1-w*t2;
			}
		}
	}
	if(type!=1){
		RG double inv = 1.0/n;
		for(i=0; i<n; i++) a[i]=a[i]*inv;
	} 
}
int n,m,l,ans[maxn];
char s[maxn],ss[maxn],Ans[maxn];
int MAIN(){
#define HAHA LALA
#ifdef HAHA
	freopen("Keller_God.in", "r", stdin);
	freopen("Keller_God.out", "w", stdout);
#endif
	scanf("%s", s);
	m = strlen(s);
	for(int i=0; i<m; i++) a[i]=Complex(s[m-i-1]-'0');
	n=1; for(; n<m; n<<=1); n<<=1;
	l=0; for(; (1<<l)<n; l++); l--;
	for(int i=1; i<n; i++) rev[i]=rev[i>>1]>>1|((i&1)<<l);
	FFT(a, n, 1);
	for(int i=0; i<n; i++) b[i]=a[i]*a[i];
	FFT(b, n, -1);
	m*=2;
	for(int i=0; i<m; i++) ans[i]=round(b[i].x);
	for(int i=0; i<m; i++) ans[i+1]+=ans[i]/10, ans[i]%=10;
	for(; ans[m]; m++) ans[m+1]=ans[m]/10, ans[m]%=10;
	for(; m>1 && !ans[m-1]; m--);
	for(int i=m-1; ~i; i--) Ans[m-i-1]=(char)(ans[i]+'0');
	memset(ss, '0', sizeof ss); ss[233] = '\0';
	printf("%s.", Ans); printf("%s\n", ss);
 	printf("%s.", Ans); printf("%s\n", ss);
 	printf("%s.", Ans); printf("%s\n", ss);
	return 0; 
}
int Wocao = MAIN();
int main(){;}