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

            

            


            
	
		

            常用鏈接
            

		

            統(tǒng)計(jì)
            
	
		

            積分與排名
            


		
		
            百事通
            
		
				
			
	

		

            最新評(píng)論
	
            

            
	
			
		

            
		
	

            

            
	
					
	
            
		
            
			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) 評(píng)論(6)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評(píng)論
            
	
	
			
            
				# re: hdu 1402 A * B Problem Plus 
					
						2009-10-13 20:18
					
				zhou
			
            
			
            
				這題真難呀?。。。?nbsp; 回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: hdu 1402 A * B Problem Plus 
					
						2009-10-13 20:20
					
				啊是
			
            
			
            
				嗯  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: hdu 1402 A * B Problem Plus 
					
						2009-10-13 20:35
					
				zhou
			
            
			
            
				回復(fù)這么快!!! ORZ ORZ!!!  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: hdu 1402 A * B Problem Plus 
					
						2009-10-13 20:36
					
				啊是
			
            
			
            
				連接到Q了呀  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: hdu 1402 A * B Problem Plus 
					
						2010-01-16 00:43
					
				abilitytao
			
            
			
            
				請(qǐng)問(wèn)有什么這方面的資料嗎？我最近也想研究這個(gè)問(wèn)題 希望能和你交流^_^

            我的QQ是 64076241  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: hdu 1402 A * B Problem Plus 
					
						2011-04-03 23:13
					
				xiaomai
			
            
			
            
				這題，太惡心了  回復(fù)  更多評(píng)論
				  
			
            
		

            




            






            

				

            



    
    







            
	   
	



久久久亚洲欧洲日产国码aⅴ|
国产精品一区二区久久|
久久久久久九九99精品|
午夜精品久久久久久|
成人a毛片久久免费播放|
99久久精品国产高清一区二区|
中文字幕人妻色偷偷久久|
噜噜噜色噜噜噜久久|
久久激情五月丁香伊人|
99久久精品费精品国产
|
久久久久噜噜噜亚洲熟女综合|
久久99精品久久久久久|
久久免费高清视频|
亚洲天堂久久精品|
久久这里有精品视频|
四虎影视久久久免费观看|
久久国产亚洲精品|
久久精品国产网红主播|
久久最近最新中文字幕大全|
久久e热在这里只有国产中文精品99|
久久精品无码一区二区三区日韩|
久久男人中文字幕资源站|
久久综合久久美利坚合众国|
欧美午夜精品久久久久免费视|
国内精品久久久久久99蜜桃|
久久精品国产精品亜洲毛片|
亚洲色大成网站www久久九|
97久久久久人妻精品专区|
久久久精品波多野结衣|
久久99久国产麻精品66|
久久久久久久尹人综合网亚洲
|
久久99国产精品久久久|
欧美久久久久久午夜精品|
囯产极品美女高潮无套久久久|
国产午夜久久影院|
中文字幕无码久久人妻|
久久中文字幕一区二区|
欧美精品国产综合久久|
国产精品99久久不卡|
久久亚洲精品人成综合网
|
久久亚洲AV成人无码电影|