出題互測(cè)測(cè)試數(shù)據(jù)圖中圖

1、圖中圖【問(wèn)題描述】在看過(guò)碟中諜后，對(duì)“X 中 X”很感，于是想探究“圖中圖”?！皥D中圖”的外圖是一張由個(gè)大節(jié)點(diǎn)組成的有條邊(無(wú)重邊和自環(huán))的無(wú)向無(wú)權(quán)圖(不一定連通)，外圖中的每個(gè)大節(jié)點(diǎn)的內(nèi)部又是一張由若干條邊組成的無(wú)向圖。想要構(gòu)一張“圖中圖”，對(duì)大節(jié)點(diǎn)之間的邊可以隨便連條，對(duì)每個(gè)大節(jié)點(diǎn)內(nèi)部的無(wú)向圖，有一種生成方法：先確定一個(gè)長(zhǎng)度為的序列對(duì)于每個(gè)大節(jié)點(diǎn)，確定一個(gè)在中的區(qū)間, 那么在第個(gè)大節(jié)點(diǎn)中， + 3邊數(shù) =區(qū)間,中存在其中為在區(qū)間, 中比小的數(shù)字個(gè)數(shù)，為區(qū)間, 中等于的數(shù)字個(gè)數(shù)。設(shè)為在區(qū)間, 中出現(xiàn)的不重復(fù)的數(shù)字個(gè)數(shù)，那么每條邊上的權(quán)值可以取1的任意正整數(shù)。現(xiàn)在，想要求出在給定, ,序列和每

2、個(gè)大節(jié)點(diǎn)的區(qū)間, 的情況下，有多少?gòu)埐煌摹皥D中圖”，由于方案數(shù)可能很大，你只需要輸出方案數(shù)模后的 。*對(duì)于大節(jié)點(diǎn)，只關(guān)心邊的情況，而不關(guān)心點(diǎn)的情況，每個(gè)大節(jié)點(diǎn)中的邊是有標(biāo)號(hào)的，兩個(gè)方案不同當(dāng)且僅當(dāng)，個(gè)大節(jié)點(diǎn)的連接狀況不同或者至少其中有一個(gè)大節(jié)點(diǎn)的其中一條邊的權(quán)值不同。【解題】這道題目是自己 YY 的一道題，第一次自己 YY 題，實(shí)在有些渣，算法一眼就知道了。勿噴。享受比賽過(guò)程最重要。平均分 300 分是目標(biāo)。對(duì)于這道題目，其實(shí)把題目簡(jiǎn)化就是求： =1(1)/2對(duì)于,相當(dāng)于是給了一個(gè)序列和一段區(qū)間, ,求3( + )區(qū)間 , 中存在 為區(qū)間, 中不同的數(shù)字的個(gè)數(shù)，為區(qū)間中小于的數(shù)字個(gè)數(shù)， _為

3、區(qū)間中等于的數(shù)字個(gè)數(shù)。算法一：對(duì)于的兩部分，可以分開(kāi)來(lái)求。那么對(duì)于 =1可以先對(duì)所有數(shù)字離散化，那么序列中的數(shù)字都在1之間，然后枚舉每一個(gè)區(qū)間，然后枚舉, 中的每一個(gè)數(shù)字，用一個(gè)數(shù)組每個(gè)數(shù)字的出現(xiàn)次數(shù)。接著，枚舉每一種數(shù)字，用前綴和地來(lái)計(jì)算不同數(shù)字種數(shù)以及：數(shù)字個(gè)數(shù)，就能方便( + 3)區(qū)間,中存在然后再用快速冪計(jì)算3( + ) 區(qū)間 , 中存在 那么計(jì)算這部分的復(fù)雜度就是()接著，再來(lái)計(jì)算(1)/2令 = (1), = ,那么也就是計(jì)算(0 106且!()!為質(zhì)數(shù)。那么由定理：當(dāng)(, ) = 1時(shí)，() 1 ( ) 得到!在模下就是(!)()1，( )!同理。的就可以預(yù)處理出1 2的! 和(

4、!)1 ,然那么后(1)求出組合數(shù)。空間復(fù)雜度：( + 2)時(shí)間復(fù)雜度：( + 2)期望得分：30分算法二：對(duì)于 50%的數(shù)據(jù)，數(shù)據(jù)只對(duì), 有制約，而卻不再是質(zhì)數(shù)。那么，對(duì)于前面的那部分，還是可以按算法一的來(lái)求，對(duì)于組合數(shù)，可以先對(duì)進(jìn)行因式分解， = 1 2 ,求出對(duì)每個(gè)的，然12 _后用中國(guó)剩余定理進(jìn)行合并。然后，問(wèn)題就變成了如何求 = 1 = 12!, 這 里 (, ) = (, ) = 1 ， 如 果令=!()!21 2 ，那么 = 0;否則， = 12 ,因?yàn)?, ) = 1,所以(, ) = 1,所以1 = ()1 。那么就是如何求!中包含的的個(gè)數(shù)以及!除去所有包含的后模的值。先解決

5、第一問(wèn)：! = 1 2 3 ,那么把他按模分類(lèi)，所有模不為0 的，可以先排除，對(duì)所有模為 0 的在這一次能貢獻(xiàn)出個(gè),然后對(duì)所有模為 0 的都除以,那么問(wèn)題就劃歸成求 !中包含的個(gè)數(shù)，那么可以遞歸進(jìn)行，復(fù)雜度為log 。代碼如下：Factor_Num(64 x)s=0;for (;x;x/=p) s+=x/p; return s;然后是第二問(wèn)：同樣，對(duì)!按模分類(lèi)，然后把連續(xù)的個(gè)一起算，那么這一層對(duì)的貢獻(xiàn)是 + , 然后對(duì)所有模為 0 的都除以,那么問(wèn)題就劃歸成求 !中除去后的乘積，那么也可以遞歸進(jìn)行,復(fù)2雜度為(log )其中為1中所有不能被整除的數(shù)的乘積。代碼如下：Calc_Except_P(

6、64 x)s=1;for (;x;x/=p)s=( return s;64)s*er(jcmo,x/mo,mo) % mo*jcx % mo % mo;空間復(fù)雜度：( + 105)2時(shí)間復(fù)雜度：( + 的質(zhì)因子數(shù) (105 + (log 105) )期望得分：50分 _算法三：其實(shí)，算法三完全是賣(mài)萌的。太水了。對(duì)于求組合數(shù)的部分，已經(jīng)滿(mǎn)足時(shí)間復(fù)雜度要求了，那么就是如何優(yōu)化第一部分求區(qū)間的時(shí)間復(fù)雜度了。本來(lái)題目在那個(gè)指數(shù)上不是三次方，是想要四次方的。然后邪惡的爆了 ,那么又要對(duì)指數(shù)對(duì)各個(gè)質(zhì)因子的模，最后也用中國(guó)剩余定理合并，并且由于算 先要對(duì)提出,然后判斷 是否超過(guò)，那么程序會(huì)比較麻煩，所以就出

7、了三次方，那么指數(shù)上的爆 的，所以可以先求出來(lái)，然后快速冪。然后就是怎么求？最大也是不會(huì)由于是區(qū)間數(shù)字統(tǒng)計(jì)類(lèi)型的題，所以很容易就想到了需要的方法。把所有詢(xún)問(wèn)區(qū)間按首端點(diǎn)的排序，然后把首端點(diǎn)在 ( + 1) 的一起做。具體方法就是枚舉,表示當(dāng)前要做區(qū)間首端點(diǎn)在( 1) 的詢(xún)問(wèn)，把所有這些區(qū)間到相應(yīng)的末端點(diǎn)處，然后枚舉從 到,3時(shí)刻當(dāng)前的( + ) 以及當(dāng)前不同的數(shù)字?jǐn)?shù)，每到一 , 區(qū)間中存在 這些數(shù)字，求出個(gè)區(qū)間的末端點(diǎn)處，的，然后在把這些數(shù)字去掉。然后就是怎么計(jì)算和刪除數(shù)字對(duì)的影響。一個(gè)數(shù)字：首先對(duì)3 的影響= ( + 1)3 3,然后是對(duì)影響=比大的不同的數(shù)字個(gè)數(shù)，如果原來(lái)是沒(méi)有的，那的影響：么會(huì)產(chǎn)生主動(dòng)影響=比小的數(shù)字?jǐn)?shù)量，并且不同的數(shù)字?jǐn)?shù)量加一。刪除一個(gè)數(shù)字：首先對(duì)3 的影響= ( 1)3 3,然后是對(duì)影響=-比大的不同的數(shù)字個(gè)數(shù)，如果原來(lái)是一個(gè)的，那的影響：么會(huì)產(chǎn)生主動(dòng)影響=-比小的數(shù)字?jǐn)?shù)量，并且不同的數(shù)字