原創(chuàng)problem12寶石紀念幣_第1頁
原創(chuàng)problem12寶石紀念幣_第2頁
全文預覽已結束

付費下載

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

寶石紀念幣題解考慮這樣一個子問題，用m不同顏色的寶石（不一定全用這可以利用Polya定理求解所有的置換共有n即順時針一格兩格…n順時針旋轉k的置換顯然可以表示成(n,k1 (n,k個長為n的循環(huán)。因此，這個子問題的答案就是：nm (n,

k現(xiàn)在原問題要求的是恰好使用了17種顏色的寶石的方案數(shù) 17

m117 (n,k)故由容斥原理，答案為：n

mm m1 k 計算中的一些細節(jié)問題這里先這些問題后文就不再一一敘述（1）由于求和最后要除以n，所以應該保存答案modn10len的結果也就是說，高精度的最后len為都是mod10位，但第len+1位無法避免小減大。因此要。第len+1位要退n，而不是10，（3）120直接處理較長，可考慮為壓縮，2一縮、3一縮、4位一縮都是可以考慮的，考慮到int64longint計算慢很多使用3一縮。，下介紹算法度為O(cn2len2。其中c顏色數(shù)17，len輸出長度120。時間復雜度為O(clen2nlogn)。同的m循環(huán)一次，保留計算的結果，時間復雜度為O(cnlen2。算法（標準算法注意到對于不同的k(n,k)的值相等m(n,k的值也是相等的因此考慮統(tǒng)計有多少個k(nk的值為給定的正整數(shù)t。由于(nk)t

t|

，所以這樣的kn個 tk,n tt tt n所以n

m(n,k

nmt k

t|n(k

注意到n是可以在O(d(n))時間內全部算出（其中d(n)表示 t ，于時間復雜度為O(clen2d(nlogn。對于3的時間來說是足夠了。算法五：這里再給出一種DP的思路，盡管時間復雜度較高，但也能得一定的分數(shù)為1,2…n。再規(guī)定17種顏色出現(xiàn)的順序。記DPi,j表示到位置i為止恰好出現(xiàn)j顏色的方案數(shù)。則可寫出狀態(tài)轉移方程：注意到不涉及高精度與高精度乘法而只涉及高精度數(shù)與低度數(shù)的乘法，故計算所有DPi,j的時間復雜度為O(cnlen)不過需要注意的是，17!DPn,17不是最終的答案，因為循環(huán)的安n會導致重復計算。正確的方法是使用容斥原理。具體推導過程不再出，最后的公式是 n

。依舊不涉及高精度數(shù)與高精度nt

t 的乘法。總時間復雜度是O(cnlen)（在這個算法基礎上，利用矩陣乘法可加速DP，但無法避免高精度數(shù)與高精度數(shù)的乘法時間復雜度O(c3lognlen2d

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間，僅對用戶上傳內容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯(lián)系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論