注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2179]FFT快速傅立叶  

2014-07-20 21:21:35|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Description

给出两个n位10进制整数x和y,你需要计算x*y。

Input

第一行一个正整数n。 第二行描述一个位数为n的正整数x。 第三行描述一个位数为n的正整数y。

Output

输出一行,即x*y的结果。

Sample Input

1
3
4

Sample Output

12

HINT

n<=60000

 

Solution

  今天终于把数论版的弄好了。之前好像是因为1LL没加调不出来。

  觉得压4位会快很多,但是Wa了半天,不管了。。。


/**************************************************************
Problem: 2179
User: wjy1998
Language: C++
Result: Accepted
Time:656 ms
Memory:19848 kb
****************************************************************/

#include<cstdio>
#include<cmath>
#include<cstring>
const double PI=acos(-1);
struct P{double x,y;};
P operator+(const P&a,const P&b){return (P){a.x+b.x,a.y+b.y};}
P operator-(const P&a,const P&b){return (P){a.x-b.x,a.y-b.y};}
P operator*(const P&a,const P&b){double d=a.x*b.x,e=a.y*b.y,f=(a.x+a.y)*(b.x+b.y);return (P){d-e,f-e-d};}

int a[270000],b[270000],n,m,k;
P w[2][270000],x[270000],y[270000];
void FFT(P*x,int k,int v)
{
int i,j,l;P tmp;
for(i=j=0;i<k;i++)
{
if(i>j)tmp=x[i],x[i]=x[j],x[j]=tmp;
for(l=k>>1;(j^=l)<l;l>>=1);
}
for(i=2;i<=k;i<<=1)
for(j=0;j<k;j+=i)
for(l=0;l<i>>1;l++)
{
tmp=x[j+l+(i>>1)]*w[v][k/i*l];
x[j+l+(i>>1)]=x[j+l]-tmp;
x[j+l]=x[j+l]+tmp;
}
}
char s[60010];
void gett(int*c)
{
scanf("%s",s);int i,len=strlen(s);m=(len+1)/2;
for(i=0;i<len;i++)c[(len-1-i)/2]=c[(len-1-i)/2]*10+s[i]-'0';
}

int main(){
scanf("%d",&n);int i,j;m=n>>1;gett(a);gett(b);
n=m;for(k=1;k<n<<1;k<<=1);
for(i=0;i<=k;i++)w[1][k-i]=w[0][i]=(P){cos(PI*2*i/k),sin(PI*2*i/k)};
for(i=0;i<k;i++)x[i]=(P){a[i],0};FFT(x,k,0);
for(i=0;i<k;i++)y[i]=(P){b[i],0};FFT(y,k,0);
for(i=0;i<k;i++)x[i]=x[i]*y[i];FFT(x,k,1);
for(i=0;i<2*k;i++)a[i]=(int)(x[i].x/k+0.5);
for(i=0;i<2*k-1;i++)
a[i+1]+=a[i]/100,a[i]%=100;
k=2*k-1;while(!a[k])k--;
printf("%d",a[k]);
for(i=k-1;~i;i--)printf("%02d",a[i]);
}

/**************************************************************
    Problem: 2179
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1160 ms
    Memory:2928 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<cstring>
const int P=479<<21|1;
typedef long long ll;
ll power(ll t,int k,int mod){ll f=1;for(;k;k>>=1,t=t*t%mod)if(k&1)f=f*t%mod;return f;}
int a[132000],b[132000],n,m,k,w[2][132000],f;
void FFT(int x[],int k,int v)
{
    int i,j,l,tmp;
    for(i=j=0;i<k;i++)
    {
        if(i>j)tmp=x[i],x[i]=x[j],x[j]=tmp;
        for(l=k>>1;(j^=l)<l;l>>=1);
    }
    for(i=2;i<=k;i<<=1)
    for(j=0;j<k;j+=i)
    for(l=0;l<i>>1;l++)
    {
        tmp=1LL*x[j+l+(i>>1)]*w[v][k/i*l]%P;
        x[j+l+(i>>1)]=(1LL*x[j+l]-tmp+P)%P;
        x[j+l]=(1LL*x[j+l]+tmp)%P;
    }
}
char s[60010];
void gett(int*c)
{
    scanf("%s",s);int i,len=strlen(s);m=(len+1)/2;
    for(i=0;i<len;i++)c[(len-1-i)/2]=c[(len-1-i)/2]*10+s[i]-'0';
}
int main(){
    scanf("%d",&n);int i,j;gett(a);gett(b);
    n=m;for(k=1;k<n<<1;k<<=1);
    w[0][0]=w[0][k]=1;j=power(3,(P-1)/k,P);
    for(i=1;i<k;i++)w[0][i]=1LL*w[0][i-1]*j%P;
    for(i=0;i<=k;i++)w[1][i]=w[0][k-i];
    FFT(a,k,0);FFT(b,k,0);
    for(i=0;i<k;i++)a[i]=1LL*a[i]*b[i]%P;
    FFT(a,k,1);j=power(k,P-2,P);
    for(i=0;i<2*k-1;i++)a[i]=1LL*a[i]*j%P;
    for(i=0;i<2*k-1;i++)
    a[i+1]+=a[i]/100,a[i]%=100;
    k=2*k-1;while(!a[k])k--;
    printf("%d",a[k]);
    for(i=k-1;~i;i--)printf("%02d",a[i]);
}



  评论这张
 
阅读(38)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018