• <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>
            

    
            

            




            







												


        

            
	

            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 此最相思 閱讀(1899) 評論(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
			
            
			
            
				這題，太惡心了  回復  更多評論
				  
			
            
		

            




            






            

				

            



    
    







            
	   
	



久久精品免费全国观看国产|
久久精品中文字幕大胸|
91秦先生久久久久久久|
日本精品久久久久中文字幕8|
色综合久久88色综合天天|
性欧美大战久久久久久久久|
久久成人18免费网站|
亚洲国产精品久久|
伊人精品久久久久7777|
久久97久久97精品免视看秋霞|
国产成人无码精品久久久免费|
精品久久久久成人码免费动漫
|
久久影视综合亚洲|
欧美黑人激情性久久|
av无码久久久久久不卡网站|
亚洲精品国产字幕久久不卡|
久久夜色精品国产亚洲|
色婷婷久久综合中文久久一本|
亚洲欧洲日产国码无码久久99|
久久夜色精品国产|
色综合久久中文色婷婷|
无码人妻少妇久久中文字幕蜜桃|
久久精品国产清自在天天线|
亚洲国产精品久久久久婷婷软件
|
国产精品久久久久国产A级|
热RE99久久精品国产66热|
AA级片免费看视频久久|
国产精品久久影院|
精品无码久久久久久尤物|
亚洲精品高清国产一线久久|
人妻无码精品久久亚瑟影视|
国产一区二区久久久|
香蕉久久影院|
久久午夜免费视频|
思思久久99热只有频精品66|
免费无码国产欧美久久18|
亚洲精品无码专区久久同性男|
久久本道久久综合伊人|
亚洲а∨天堂久久精品|
久久久久亚洲AV无码观看|
精品国产乱码久久久久软件|