• <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>
            隨筆 - 68  文章 - 57  trackbacks - 0
            <2009年5月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            常用鏈接

            留言簿(8)

            隨筆分類(74)

            隨筆檔案(68)

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

              對于兩個n階多項式的乘法,如果模擬做的話復雜度為O(n^2),利用快速傅里葉變換可以把復雜度降到O(nlogn)。
              多項式有兩種表示:系數形式和點值表示。如果把兩個多項式寫成點值形式,那么相乘的復雜度就是O(n)的。FFT的基本思想就是通過把系數形式化成點值形式,相乘之后再化回來,使得復雜度降到O(nlogn)。具體就是先通過巧妙地選取n個復數單位根,利用復數的一些非常好的性質求得DFT,把這一步的復雜度降到O(nlogn),然后將得到的點值相乘后,利用插值再變換成系數形式。插值的過程居然和求DFT的過程驚人的相似,復雜度依然為O(nlogn)。
              在實現的時候基本參照算法導論,感覺遞歸不太好寫,就寫了個迭代的。N久不用復數了,連基本運算都忘了,導致實現的時候出了一堆錯,后來好不容易寫好了,結果卻一點都不靠譜。查了好久才發現,初始w是1的時候,我把實部和虛部都設成1了,囧。實際上虛部應該是0。改完后發現多項式的表示又出了問題,后來發現我把系數的順序寫反了。然后利用這個做了HDU 1402,就是高精度乘法。WA了幾次,很抓狂。后來寫了一個程序跑了一組極限數據,居然掛了。仔細觀察后發現是精度的問題。因為FFT中間運算過程都是浮點數,但是最后要輸出整數,取整的時候舍入精度出了問題,加了1e-3之后過了。
              還有一道比較巧妙的FFT的題目,SRM 436 DIV 1 1000pt,做的時候開始Z0忘記取模了,結果還以為是模板的問題,找了很長時間才發現。做題還是要細心啊。
            posted on 2009-05-18 16:01 sdfond 閱讀(550) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm - Ad Hoc
            无码人妻精品一区二区三区久久 | 日韩人妻无码精品久久免费一| 久久综合亚洲色HEZYO国产| 日韩精品久久久久久久电影蜜臀| 亚洲色婷婷综合久久| 久久精品人人做人人爽电影| 91精品国产色综合久久| 精品久久久久久无码国产| 一本久久免费视频| 久久99国产乱子伦精品免费| 91精品国产91久久久久久蜜臀 | 欧美午夜A∨大片久久| 久久人人爽人人爽人人片AV不 | 一本久久a久久精品亚洲| 久久水蜜桃亚洲av无码精品麻豆| 精品欧美一区二区三区久久久| 亚洲国产精品无码久久SM| 一本一道久久综合狠狠老| 久久久久久噜噜精品免费直播| 国产精品九九久久精品女同亚洲欧美日韩综合区| 少妇久久久久久被弄高潮| 国产精品无码久久四虎| 伊人久久五月天| 国产99久久久国产精免费| 久久精品一本到99热免费| 国产亚洲精久久久久久无码AV| 精品国产91久久久久久久| 国内精品久久久久久麻豆| 久久天天躁狠狠躁夜夜网站| 一本色综合久久| 91精品国产高清91久久久久久| 久久精品国产亚洲AV蜜臀色欲| 91久久精一区二区三区大全| 久久婷婷五月综合97色一本一本| 久久国产劲爆AV内射—百度| 久久国产精品99精品国产| 久久久久久国产精品美女| 中文字幕久久精品| 色综合久久天天综线观看| 久久精品国产亚洲av日韩| 久久久久国产精品熟女影院|