青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

misschuer

常用鏈接

統計

積分與排名

百事通

最新評論

hdu 1402 A * B Problem Plus

http://acm.hdu.edu.cn/showproblem.php?pid=1402
#include<iostream>
#include
<cmath>
using namespace std;
typedef 
struct vir{
        
double re,im;
        vir()
{}
        vir(
double a,double b){re=a;im=b;}
        vir 
operator +(const vir &b)return vir(re+b.re,im+b.im);}
        vir 
operator -(const vir &b)return vir(re-b.re,im-b.im);}
        vir 
operator *(const vir &b)return vir(re*b.re-im*b.im,re*b.im+b.re*im);}
}
vir;
vir x1[
200005],x2[200005];
const double Pi = acos(-1.0);
void change(vir *x,int len,int loglen)
{
        
int i,j,k,t;
        
for(i=0;i<len;i++)
        
{
                t 
= i;
                
for(j=k=0;j<loglen;j++,t>>=1)
                        k 
= (k<<1)|(t&1);
                
if(k<i)
                
{
                        vir wt 
=  x[k];
                        x[k] 
= x[i];
                        x[i] 
= wt;
                }

        }

}

void fft(vir *x,int len,int loglen)
{
        
int i,j,t,s,e;
        change(x,len,loglen);
        t 
= 1;
        
for(i=0;i<loglen;i++,t<<=1)
        
{
                s 
= 0;
                e 
= s + t;
                
while(s<len)
                
{
                        vir a,b,wo(cos(Pi
/t),sin(Pi/t)),wn(1,0);
                        
for(j=s;j<s+t;j++)
                        
{
                                a 
= x[j];
                                b 
= x[j+t]*wn;
                                x[j] 
= a + b;
                                x[j
+t] = a - b;
                                wn 
=wn*wo;
                        }

                        s 
= e+t;
                        e 
= s+t;
                }

        }

}


void dit_fft(vir *x,int len,int loglen)
{
        
int i,j,s,e,t=1<<loglen;
        
for(i=0;i<loglen;i++)
        
{
                t
>>=1;
                s
=0;
                e
=s+t;
                
while(s<len)
                
{
                        vir a,b,wn(
1,0),wo(cos(Pi/t),-sin(Pi/t));
                        
for(j=s;j<s+t;j++)
                        
{
                                a 
= x[j]+x[j+t];
                                b 
= (x[j]-x[j+t])*wn;
                                x[j] 
= a;
                                x[j
+t] = b;
                                wn 
= wn*wo;
                        }

                        s 
= e+t;
                        e 
= s+t;
                }

        }

        change(x,len,loglen);
        
for(i=0;i<len;i++)
                x[i].re
/=len;
}



int main()
{
        
char a[100005],b[100005];
        
int i,len1,len2,t,over,len,loglen;
        
        
while(scanf("%s%s",a,b)!=EOF)
        
{
                len1 
= strlen(a)<<1;
                len2 
= strlen(b)<<1;
                len 
= 1;
                loglen 
= 0;
                
while(len<len1)
                
{
                        len
<<=1;
                        loglen
++;
                }

                
while(len<len2)
                
{
                        len
<<=1;
                        loglen
++;
                }

                
for(i=0;a[i]!='\0';i++)
                
{
                        x1[i].re 
= a[i]-'0';
                        x1[i].im 
= 0;
                }

                
for(;i<len;i++)
                        x1[i].re 
= x1[i].im = 0;
                
for(i=0;b[i]!='\0';i++)
                
{
                        x2[i].re 
= b[i]-'0';
                        x2[i].im 
= 0;
                }

                
for(;i<len;i++)
                        x2[i].re 
= x2[i].im = 0;
                fft(x1,len,loglen);
                fft(x2,len,loglen);
                
for(i=0;i<len;i++)
                        x1[i] 
= x1[i]*x2[i];
                dit_fft(x1,len,loglen);
                
for(i=(len1+len2)/2-2,over=loglen=0;i>=0;i--)
                
{
                        t 
= x1[i].re + over + 0.5;
                        a[loglen
++= t%10;
                        over 
=  t/10;
                }

                
while(over)
                
{
                        a[loglen
++= over%10;
                        over 
/= 10;
                }

                
for(loglen--;loglen>=0&&!a[loglen];loglen--);
                
if(loglen<0)
                        putchar(
'0');
                
else
                        
for(;loglen>=0;loglen--)
                                putchar(a[loglen]
+'0');
                putchar(
'\n');
        }

        
return 0;
}

posted on 2009-04-18 15:59 此最相思 閱讀(1908) 評論(6)  編輯 收藏 引用

評論

# re: hdu 1402 A * B Problem Plus 2009-10-13 20:18 zhou

這題真難呀?。。?!  回復  更多評論   

# re: hdu 1402 A * B Problem Plus 2009-10-13 20:20 啊是

嗯  回復  更多評論   

# re: hdu 1402 A * B Problem Plus 2009-10-13 20:35 zhou

回復這么快!!! ORZ ORZ!!!  回復  更多評論   

# re: hdu 1402 A * B Problem Plus 2009-10-13 20:36 啊是

連接到Q了呀  回復  更多評論   

# re: hdu 1402 A * B Problem Plus 2010-01-16 00:43 abilitytao

請問有什么這方面的資料嗎?我最近也想研究這個問題 希望能和你交流^_^
我的QQ是 64076241  回復  更多評論   

# re: hdu 1402 A * B Problem Plus 2011-04-03 23:13 xiaomai

這題,太惡心了  回復  更多評論   


只有注冊用戶登錄后才能發表評論。
網站導航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            日韩系列在线| 国产精品高精视频免费| 亚洲综合不卡| 欧美经典一区二区| 免费不卡视频| 国产最新精品精品你懂的| 一区二区三区**美女毛片| 亚洲区一区二| 狂野欧美激情性xxxx欧美| 久久免费偷拍视频| 国产精品最新自拍| 中文av一区特黄| 中日韩在线视频| 欧美精品一区二区久久婷婷| 乱码第一页成人| 国际精品欧美精品| 久久精品国产在热久久| 欧美一区二区网站| 国产乱码精品一区二区三区av| 9久re热视频在线精品| 一区二区免费看| 欧美日韩成人| 在线亚洲激情| 香蕉成人久久| 国模 一区 二区 三区| 欧美在线影院| 免费成人性网站| 91久久夜色精品国产九色| 欧美不卡视频一区发布| 欧美激情亚洲精品| 亚洲精品久久| 欧美日本韩国一区| 在线中文字幕一区| 久久精品99国产精品| 国产一区二区三区在线播放免费观看| 欧美在线3区| 猛男gaygay欧美视频| 亚洲日本理论电影| 欧美日韩免费观看中文| 一区二区三区你懂的| 欧美一区亚洲二区| 好吊视频一区二区三区四区| 猛干欧美女孩| 99国产精品久久久久久久| 午夜在线视频一区二区区别| 国产亚洲精品久久久| 美女主播一区| 一区二区三区精密机械公司| 欧美主播一区二区三区| 激情一区二区| 欧美精品久久久久久久| 亚洲综合电影| 免费人成精品欧美精品| 在线一区二区视频| 国产女主播一区二区| 老司机精品视频一区二区三区| 亚洲精品黄网在线观看| 午夜伦理片一区| 揄拍成人国产精品视频| 欧美日韩精品欧美日韩精品一| 亚洲欧美中文日韩在线| 欧美激情一区二区在线 | 欧美精品午夜| 午夜欧美大片免费观看| 亚洲福利精品| 久久男女视频| 亚洲自拍偷拍一区| 亚洲精品一级| 国产午夜一区二区三区| 欧美日韩不卡| 另类综合日韩欧美亚洲| 亚洲免费在线看| 亚洲国产精品一区二区久| 久久99伊人| 国产精品99久久久久久白浆小说| 红桃视频一区| 国产三区精品| 国产精品久久久久永久免费观看| 欧美1级日本1级| 久久久精品国产99久久精品芒果| 99在线观看免费视频精品观看| 美女91精品| 久久精品在线| 欧美一级网站| 亚洲女ⅴideoshd黑人| 99riav国产精品| 亚洲国产欧洲综合997久久| 国产精品久久久久久久app| 欧美成人精品一区二区三区| 久久精品五月| 欧美一区2区视频在线观看| 在线视频中文亚洲| 亚洲精品综合精品自拍| 亚洲第一页中文字幕| 毛片一区二区三区| 久久精品一区二区三区不卡| 性欧美在线看片a免费观看| 亚洲一区二区不卡免费| 一区二区精品| 一区二区高清| 99在线精品视频在线观看| 亚洲日本成人女熟在线观看| 亚洲国产经典视频| 亚洲国产精品一区二区www| 国语自产精品视频在线看| 国产主播一区| 在线观看日韩www视频免费| 黄色欧美成人| 在线免费一区三区| 韩国欧美一区| 在线观看欧美日韩国产| 亚洲电影免费在线| 亚洲欧洲日夜超级视频| 亚洲三级性片| 中文在线一区| 午夜欧美精品| 久久成人资源| 美女视频黄a大片欧美| 欧美激情一区二区三区在线视频观看| 欧美二区在线看| 亚洲美女中文字幕| 亚洲视频综合| 久久精品视频亚洲| 欧美大尺度在线| 欧美日韩一区二区三区免费看| 国产精品成av人在线视午夜片| 国产精品女人毛片| 国产亚洲精品美女| 亚洲国产日韩欧美在线图片| 99在线热播精品免费| 亚洲免费在线观看视频| 久久久午夜视频| 最新国产乱人伦偷精品免费网站| 亚洲免费成人| 性欧美暴力猛交69hd| 久久视频一区二区| 欧美日韩卡一卡二| 国产视频在线观看一区| 亚洲国产精品99久久久久久久久| 一本到高清视频免费精品| 欧美在线一级视频| 亚洲第一精品夜夜躁人人爽| 夜夜嗨av一区二区三区免费区| 欧美一区二区三区的| 欧美激情亚洲国产| 国产亚洲一区在线| 99re6热只有精品免费观看| 久久精品人人做人人综合| 亚洲成色最大综合在线| 亚洲在线成人精品| 免费日韩精品中文字幕视频在线| 国产精品久久久久9999| 亚洲福利一区| 久久av老司机精品网站导航| 欧美黄网免费在线观看| 亚洲欧美一区二区三区极速播放| 欧美不卡一区| 国内精品免费午夜毛片| 亚洲一区在线播放| 欧美电影打屁股sp| 午夜日韩电影| 国产精品99免视看9| 亚洲日本一区二区三区| 久久免费偷拍视频| 亚洲一区久久| 欧美午夜大胆人体| 亚洲美女色禁图| 裸体女人亚洲精品一区| 亚洲综合日本| 欧美日韩在线免费| 亚洲日本欧美| 欧美成人在线网站| 欧美在线中文字幕| 国产日本亚洲高清| 亚洲综合第一| 宅男噜噜噜66一区二区| 欧美激情四色| 亚洲美女性视频| 欧美大色视频| 久久一区二区三区国产精品 | 久久久久久久91| 亚洲欧美日韩国产综合在线 | 亚洲高清视频一区| 久久久亚洲高清| 伊人精品久久久久7777| 久久久成人网| 久久精品免视看| 狠狠色噜噜狠狠狠狠色吗综合| 欧美专区福利在线| 午夜欧美大片免费观看| 国产日韩精品综合网站| 亚洲欧美一区二区原创| 亚洲一区在线免费| 国产精品一区二区久久国产| 欧美一区二区三区在线观看| 午夜精品一区二区三区四区 | 99国产精品国产精品毛片| 欧美日韩另类综合| 亚洲午夜视频| 亚洲一区二区成人|