算法合集之p225lya計(jì)數(shù)法的應(yīng)用(參考版)
2024-10-19 20:29本頁面
【正文】 。 證明 ?要得到在置換下穩(wěn)定不動(dòng)的方案，即把置換的每個(gè)循環(huán)節(jié)都染上相同的顏色。 ?在同一等價(jià)類中，兩種著色對和貢獻(xiàn)了同樣的量，每個(gè)等價(jià)類的總貢獻(xiàn)是 |G|。 證明 ?一種計(jì)數(shù)的方式是考察 G中的每個(gè) f ，并計(jì)算 f保持著色不變的著色數(shù)，然后相加所有的量。 ?集合中 的置換個(gè)數(shù)等于 G(c)中置換的個(gè)數(shù)。 證明 ?設(shè) f 是 G 中的一個(gè)置換，根據(jù)定理 1，滿足 g*c=f*c的置換 g 實(shí)際上就是 中的那些置換。 ?證明 ?假設(shè) f*c=g*c 則 ?所以 f1 g使 c不變，因此， f1 g 屬于 G(c)。 證明 ?設(shè) c為 中的一種著色，那么與 c 等價(jià)的著色數(shù)等于 G中的置換個(gè)數(shù)除以 c 的穩(wěn)定核中的置換個(gè)數(shù)。 ?數(shù)學(xué)方法是解決問題的工具，而分析問題能力是算法的源泉。 ?靈活使用 P243。 全文總結(jié) ?P243。比如 – Transportation is fun (spoj 419) – He’ s Circles (sgu 294) – Cubes (uva 10601) ?它們在直接使用公式時(shí)往往會(huì)遇到一些困難。lya計(jì)數(shù)問題中經(jīng)常用到 ? 對于每類相似置換個(gè)數(shù)的計(jì)算，也需要扎實(shí)的數(shù)學(xué)功底。 ? 所以 T2也與 P互質(zhì) ? 由數(shù)論知識(shí)可知： ? T2p1≡1 (mod p) ? T21 ≡ T2p1 T21=T2p2 (mod p) ? 所以可以把 T21轉(zhuǎn)化為求 T2p2，可用倍增的方法在O(Logp) 的時(shí)間內(nèi)求解。 ?(1,2) (3,4,5,6) ?(1,3),(2,4),(1,5),(2,6) ?(1,4),(2,5),(1,6),(2,3) 分析 ?還需要求出與其類似的置換數(shù)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1