1、圖中圖【問題描述】在看過碟中諜后，對“X 中 X”很感，于是想探究“圖中圖”。“圖中圖”的外圖是一張由個大節點組成的有條邊(無重邊和自環)的無向無權圖(不一定連通)，外圖中的每個大節點的內部又是一張由若干條邊組成的無向圖。想要構一張“圖中圖”，對大節點之間的邊可以隨便連條，對每個大節點內部的無向圖，有一種生成方法：先確定一個長度為的序列對于每個大節點，確定一個在中的區間, 那么在第個大節點中， + 3邊數 =區間,中存在其中為在區間, 中比小的數字個數，為區間, 中等于的數字個數。設為在區間, 中出現的不重復的數字個數，那么每條邊上的權值可以取1的任意正整數。現在，想要求出在給定, ,序列和每

2、個大節點的區間, 的情況下，有多少張不同的“圖中圖”，由于方案數可能很大，你只需要輸出方案數模后的 。*對于大節點，只關心邊的情況，而不關心點的情況，每個大節點中的邊是有標號的，兩個方案不同當且僅當，個大節點的連接狀況不同或者至少其中有一個大節點的其中一條邊的權值不同。【解題】這道題目是自己 YY 的一道題，第一次自己 YY 題，實在有些渣，算法一眼就知道了。勿噴。享受比賽過程最重要。平均分 300 分是目標。對于這道題目，其實把題目簡化就是求： =1(1)/2對于,相當于是給了一個序列和一段區間, ,求3( + )區間 , 中存在 為區間, 中不同的數字的個數，為區間中小于的數字個數， _為

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

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

5、第一問：! = 1 2 3 ,那么把他按模分類，所有模不為0 的，可以先排除，對所有模為 0 的在這一次能貢獻出個,然后對所有模為 0 的都除以,那么問題就劃歸成求 !中包含的個數，那么可以遞歸進行，復雜度為log 。代碼如下：Factor_Num(64 x)s=0;for (;x;x/=p) s+=x/p; return s;然后是第二問：同樣，對!按模分類，然后把連續的個一起算，那么這一層對的貢獻是 + , 然后對所有模為 0 的都除以,那么問題就劃歸成求 !中除去后的乘積，那么也可以遞歸進行,復2雜度為(log )其中為1中所有不能被整除的數的乘積。代碼如下：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;空間復雜度：( + 105)2時間復雜度：( + 的質因子數 (105 + (log 105) )期望得分：50分 _算法三：其實，算法三完全是賣萌的。太水了。對于求組合數的部分，已經滿足時間復雜度要求了，那么就是如何優化第一部分求區間的時間復雜度了。本來題目在那個指數上不是三次方，是想要四次方的。然后邪惡的爆了 ,那么又要對指數對各個質因子的模，最后也用中國剩余定理合并，并且由于算 先要對提出,然后判斷 是否超過，那么程序會比較麻煩，所以就出

7、了三次方，那么指數上的爆 的，所以可以先求出來，然后快速冪。然后就是怎么求？最大也是不會由于是區間數字統計類型的題，所以很容易就想到了需要的方法。把所有詢問區間按首端點的排序，然后把首端點在 ( + 1) 的一起做。具體方法就是枚舉,表示當前要做區間首端點在( 1) 的詢問，把所有這些區間到相應的末端點處，然后枚舉從 到,3時刻當前的( + ) 以及當前不同的數字數，每到一 , 區間中存在 這些數字，求出個區間的末端點處，的，然后在把這些數字去掉。然后就是怎么計算和刪除數字對的影響。一個數字：首先對3 的影響= ( + 1)3 3,然后是對影響=比大的不同的數字個數，如果原來是沒有的，那的影響：么會產生主動影響=比小的數字數量，并且不同的數字數量加一。刪除一個數字：首先對3 的影響= ( 1)3 3,然后是對影響=-比大的不同的數字個數，如果原來是一個的，那的影響：么會產生主動影響=-比小的數字數量，并且不同的數字