• <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
			
            
			
            
				這題真難呀！！！！  回復(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)論
				  
			
            
		

            




            



            


            

	
            
		
		
            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            
		
            
		
				
		
		
		
            
		
            			
		
		
		
		
            
		
            
			
		
            
		
            
			
		
            
		
            
			
            網(wǎng)站導(dǎo)航:
			博客園  
			IT新聞  
			BlogJava  			
			博問(wèn)  
			Chat2DB  
			管理
			
            		
		
            
		
            
			
				

            


            

            		
		
            
	
            	

            



            

				

            



    
    







            
	   
	



久久精品无码一区二区无码|
久久A级毛片免费观看|
99久久国产综合精品网成人影院|
国产一区二区精品久久凹凸|
久久亚洲欧美国产精品|
久久久精品久久久久特色影视|
久久精品国产69国产精品亚洲|
亚洲美日韩Av中文字幕无码久久久妻妇|
成人国内精品久久久久影院|
久久久精品人妻一区二区三区蜜桃|
久久66热人妻偷产精品9|
亚洲精品白浆高清久久久久久|
久久久久亚洲AV成人网人人软件|
久久久精品久久久久影院|
久久久久一本毛久久久|
色婷婷综合久久久中文字幕|
欧美无乱码久久久免费午夜一区二区三区中文字幕
|
久久精品国产91久久综合麻豆自制|
欧美久久久久久精选9999|
精品久久久无码人妻中文字幕豆芽|
久久亚洲天堂|
久久嫩草影院免费看夜色|
麻豆精品久久精品色综合|
久久综合丁香激情久久|
日本欧美久久久久免费播放网
|
亚洲国产精品人久久|
中文国产成人精品久久不卡|
亚洲国产精品无码久久久秋霞2
|
97久久精品人人做人人爽|
久久精品国产99久久无毒不卡|
一本综合久久国产二区|
久久国产精品国语对白|
久久久久久久亚洲精品|
久久久精品日本一区二区三区|
狠狠精品干练久久久无码中文字幕
|
婷婷久久香蕉五月综合加勒比|
人妻无码αv中文字幕久久琪琪布|
久久天天躁狠狠躁夜夜96流白浆|
久久人人爽人人爽人人爽|
久久久久人妻精品一区二区三区|
久久久久国产精品人妻|