Problem A. CF626F Group Projects

有 \(n\) 個學生，每個學生有一個能力值 \(a_i\)。現(xiàn)在要把這些學生分成一些（任意數(shù)量的）組，每一組的“不和諧度”是該組能力值最大的學生與能力值最小的學生的能力值的差。求所有不和諧度之和不超過 \(k\) 的分組方案總數(shù)，答案對 \(10^9+7\) 取模。

\(1 \leq n \leq 200\)，\(0 \leq k \leq 1000\)，\(1 \leq a_i \leq 500\)。

解法：

顯然能力值順序與答案無關。從大到小排序后依次確定每個數(shù)分到那一組，此時每組的不和諧度是最先加入的數(shù)減去最后加入的數(shù)。

然后考慮 DP。記 \(f_{i,j,x}\) 表示已經(jīng)加入了前 \(i\) 個數(shù)，現(xiàn)在還有 \(j\) 組可以加入，目前不和諧度和為 \(x\)。可以加入指的是這個組還沒有確定不和諧度，即最后加入的數(shù)不確定。轉(zhuǎn)移分類討論，分別是 \(a_i\) 單獨一組一個數(shù)，或者單獨一組一個數(shù)但后面還會加入其他數(shù)，或者是加入 \(j\) 組中的某組并確定這個組之后不在加入數(shù)了，或者后面還會加入。復雜度看似是 \(O(n^2k)\)，但是 \(x\) 這一維上限是 \(O(\sum a_i)\) 的，所以復雜度為 \(O(n^2 \sum a_i)\)，無法通過。

注意整個過程不對的在于 \(x\) 這一維在決策過程中不一定單調(diào)不降，所以無法限制在 \([0,k]\) 中。但是可以發(fā)現(xiàn) \(b_k - b_1 = \sum \limits_{i=1}^{k-1} b_{i+1}-b_i\)，于是我們對于每個 \((i,j,x)\)，轉(zhuǎn)移到下一步時變?yōu)?\((i+1,j',x+j(a_{i}-a_{i+1}))\) 即可。此時 \(x\) 這一維單調(diào)不降，故復雜度為 \(O(n^2k)\)，對 \(i\) 滾動數(shù)組即可通過。

Submission Link.

Problem B. CF2001E1 Deterministic Heap (Easy Version)

題意：

給定一棵 \(n\) 層的滿二叉樹，節(jié)點編號范圍為 \([1,2^n-1]\)，并且對于任意非葉子節(jié)點 \(i\)，滿足左節(jié)點是 \(2i\)，右節(jié)點是 \(2i+1\)，并且每個點有點權(quán) \(a_i\)。

定義一次 \(\texttt{pop}\) 操作為如下：

1. 令 \(v\gets1\)。

2. 重復以下操作直到 \(v\) 是葉子節(jié)點：

   a. 對于 \(v\) 的兩個子節(jié)點，假設點權(quán)較大的一個點編號為 \(x\)。

   b. \(a_x\gets a_v\)。

   c. \(x \gets v\)。

3. \(a_v\gets -1\)。

我們定義 \(\texttt{pop}\) 操作是確定的，當且僅當滿足上述過程中，\(a_{2v}\neq a_{2v+1}\)。

定義一棵滿二叉樹是大根堆當且僅當對于所有非葉子節(jié)點 \(v\) 滿足 \(a_v\ge a_{2v}\) 且 \(a_v\ge a_{2v+1}\)。

定義一個大根堆是 \(\texttt{pop}\) 操作確定的當且僅當?shù)谝淮?\(\texttt{pop}\) 操作時 \(\texttt{pop}\) 操作是確定的。

初始時，\(a_v=0\)，定義給一個節(jié)點 \(x\) 操作一次為把 \(1\rightsquigarrow x\) 路徑上所有點點權(quán)加上 \(1\)，并求出滿足恰好操作 \(k\) 次后，不同的 \(\texttt{pop}\) 操作確定的大根堆的數(shù)量，模上 \(P\)。

多測，\(T \leq 500\)，\(1 \leq \sum n, \sum k \leq 500\)，\(10^8 \leq P \leq 10^9\)，\(P\) 是質(zhì)數(shù)。

解法：

一眼題。

考慮 DP，記 \(f_{i,j}\) 表示高度為 \(i\) 的滿二叉樹操作 \(j\) 次且 \(\texttt{pop}\) 操作確定的方案數(shù)，\(g_{i,j}\) 同理，但是不要求 \(\texttt{pop}\) 操作確定。轉(zhuǎn)移是卷積。直接做復雜度 \(O(nm^2)\)，可以通過。NTT 可以做到 \(O(nm \log m)\)。

Submission Link.

Problem C. Floyd

題意：

一般來講 \(O(n^3)\) 求無向圖任意兩點連通性的算法都用 Floyd 實現(xiàn)，示例代碼如下：

void OldFloyd(int n){
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++) if(G[i][k]){
            for(int j=1; j<=n; j++) if(G[k][j]){
                G[i][j] = 1;
            }
        }
    }
}

如果 \(n\) 比較大且執(zhí)行 Floyd 的次數(shù)較多，那么容易超時（小 C 不知道可以用 bitset 優(yōu)化做到 \(O(\frac{n^3}{w})\)）

所以小 C 想出來個奇技淫巧，他限制了 Floyd 的輪數(shù)，只讓它做 \(m\) 輪，這樣復雜度就是 \(O(n^2 \cdot m)\) 的，示例代碼如下：

void NewFloyd(int n, int m){
    for(int k=1; k<=m; k++){
        for(int i=1; i<=n; i++) if(G[i][k]){
            for(int j=1; j<=n; j++) if(G[k][j]){
                G[i][j] = 1;
            }
        }
    }
}

這樣的做法可以在某種程度上優(yōu)化求連通性的效率，但是可能會出錯，小 C 現(xiàn)在想知道，假如現(xiàn)在等概率隨機生成一張 \(n\) 個點的簡單無向圖（即對于每對 \((i, j)\) \((i < j)\)，\(g[i][j]\) 和 \(g[j][i]\) 有 \(\dfrac{1}{2}\) 的概率同時為 1，否則同時為 0。注意：這里我們默認認為對于任意的 \(i\) 都滿足 \(g[i][i] = 1\)），并經(jīng)上述代碼一輪 \(m\) 輪 Floyd 后，得到的結(jié)果完全正確的概率是多少（即執(zhí)行兩份代碼的得到的 \(G\) 數(shù)組完全相同），你只需要輸出這個概率對大質(zhì)數(shù) \(p\) 取模后的結(jié)果即可。

\(1 \leq n, m \leq 150\)，\(10^8 < p < 1.01 \times 10^9\)，\(p\) 是質(zhì)數(shù)，\(2\) 秒。

解法：

好題。

求概率等價于求方案數(shù)。

容易發(fā)現(xiàn)進行 \(m\) 輪 Floyd 本質(zhì)求出的 \(G_{i,j}\) 其實是 \(i\) 到 \(j\) 是否存在一條路徑，路徑上除了端點的點編號最大值不超過 \(m\)。

首先求出 \(h_i\) 表示 \(i\) 個點的無向簡單連通圖方案數(shù)。這個是簡單的。

其次，考慮求 \(g_{i,j}\) 表示 \(n=i,m=j\) 的無向簡單連通圖方案數(shù)，轉(zhuǎn)移考慮將 \(\leq j\) 的點與 \(>j\) 的點分開。然后考慮 \(>j\) 的所有點都要往 \(\leq j\) 的點構(gòu)成的連通圖中連至少一條邊。這部分是容易轉(zhuǎn)移的。

接著考慮求 \(f_{i,j}\) 表示 \(n=i,m=j\) 的答案。和 \(g\) 的區(qū)別在于不要求連通。轉(zhuǎn)移考慮常見方法，枚舉點 \(i\) 所在連通塊大小。但是我們還需要枚舉這個連通塊中有多少點編號 \(<j\)，總復雜度 \(O(n^4)\)，適當卡常即可通過。

Code.

代碼中 \(f\) 和 \(g\) 是反的。

Problem D. CF2001E2 Deterministic Heap (Hard Version)

題意：

定義一個堆為一棵樹高為 \(n\)，點數(shù)為 \(2^n-1\) 的滿二叉樹，點權(quán)序列為 \(\{a\}\)，對于每一個非葉子節(jié)點 \(i(1 \le i \le 2^{n-1}-1)\)，其兒子應為 \(2i\) 和 \(2i+1\)，且滿足 \(a_i \ge \max(a_{2i}, a_{2i+1})\)。

一次刪除操作的偽代碼如下：

1. 初始令 \(v=1\)。
2. 執(zhí)行 \(a_v \gets \max(a_{2v},a_{2v+1})\)，并令 \(v\) 為 \(a_{2v},a_{2v+1}\) 中較大者的下標（若相等則認為這次刪除操作不確定，\(v\) 變?yōu)?\(2v\) 或 \(2v+1\) 中任意一個）。
3. 若 \(2v+1 \le 2^{n}-1\)，返回第 2 條。
4. 執(zhí)行 \(a_v \gets -1\)。

定義一個堆是確定的，當且僅當執(zhí)行兩次刪除操作的過程中，不存在不確定的操作。

定義一個堆是可構(gòu)造的，當且僅當對于給定常數(shù) \(k\)，一個堆的點權(quán)序列可以通過以下方式構(gòu)造出：

• 初始所有 \(a_i=0\)。執(zhí)行 \(k\) 次操作，每次任選一個點 \(1 \le x \le 2^n-1\)，將根節(jié)點到 \(x\) 路徑上所有的點權(quán)加 \(1\)。

\(t\) 次詢問，每次給出 \(n,k,p\)，求有多少個樹高為 \(n\) 的可構(gòu)造的堆是確定的，答案對 \(p\) 取模。

\(t \le 50\)，\(\sum n \le 100\)，\(\sum k \le 500\)， \(10^8 \le p \le 10^9\)，\(p\) 是質(zhì)數(shù)。

解法：

對于 E1，題意區(qū)別在于確定的堆只需要滿足一次操作確定即可。其簡略做法是記 \(f_{i,j}\) 表示深度為 \(i\) 的二叉樹，進行了 \(j\) 次操作構(gòu)成的確定堆方案數(shù)，以及 \(g_{i,j}\) 表示堆不需要確定的方案數(shù)。

對于 E2，考慮如何刻畫操作兩次。可以發(fā)現(xiàn)兩次操作的第一個走向不同位置只依賴于另一個方向的兩個兒子點權(quán)最大值。考慮記 \(h_{i,j,k}\) 表示深度為 \(i\) 的堆，進行了 \(j\) 次操作，兩個兒子點權(quán)最大值為 \(k\)，且可以進行一次操作的方案數(shù)。\(s_{i,j,k}\) 表示可以進行兩次的方案數(shù)。可以發(fā)現(xiàn)轉(zhuǎn)移只需要枚舉左兒子和右兒子點權(quán)，維護前綴和即可。為了更加方便可以直接將狀態(tài)變?yōu)閮鹤幼畲笾?\(\leq k\)，復雜度 \(O(nk^2)\)，可以通過。

Submission Link.

Problem E. CF1466H Finding satisfactory solutions

題意：

有 \(n\) 個顧客與 \(n\) 個物品，每個顧客有一個排列 \(b_i\) 表示他對物品喜好程度的排名。

你有一個物品分配方案的排列 \(a\)，表示 \(i\) 號顧客拿到第 \(a_i\) 個物品。

稱一個分配方案 \(a\) 是好的，當且僅當不存在一個非空集合 \(S\)，使得存在一個分配方案 \(a'\) 滿足：

1. \(\forall i \in S, a'_i \in S\)
2. \(\forall i \in S\)，第 \(i\) 個顧客相對 \(a_i\) 更喜歡 \(a'_i\)（不要求嚴格更喜歡 \(a'_i\)，即 \(a_i\) 可以等于 \(a'_i\)）
3. \(\exists i \in S\)，第 \(i\) 個顧相對 \(a_i\) 嚴格更喜歡 \(a'_i\)。

輸入物品分配方案的排列 \(a_1,a_2,\cdots,a_n\)，請求出有多少種不同的 \(\{b_1,b_2,\cdots,b_n\}\) 排列組使得分配方案 \(a\) 是好的。可以證明對于任意一個 \(b\)，都存在唯一的好排列 \(a\)。

\(n\le 40\)，答案對 \(10^9+7\) 取模。

解法：

首先考慮為什么對于任意一個 \(b\)，都僅存在唯一的 \(a\)。

考慮構(gòu)建有向圖，對于每個 \(i\)，連邊 \(i \rightarrow b_{i,1}\)，意思是每個點向其最喜歡的物品連邊。顯然圖是一個內(nèi)向基環(huán)樹森林。不難證明每個環(huán)都是要取的，也就是環(huán)上的人獲得的物品都是其最喜歡的物品。然后將環(huán)上點刪去，對剩下點繼續(xù)建圖，每個人向第二喜歡的物品編號連邊，以此類推。顯然對應的好序列唯一確定。

考慮排列 \(a\) 構(gòu)成的圖，連邊 \(i \rightarrow a_i\)，每個環(huán)都是我們生成過程中基環(huán)樹上的一個環(huán)。繼續(xù)考慮每個人的 \(b\) 怎么確定。我們在 \(a\) 的排列構(gòu)成的圖基礎上，對于每個點 \(i\)，將其喜愛度比 \(a_i\) 更高的連邊，也就是向?qū)?\(b\) 序列中 \(a_i\) 前面的點連邊。不難發(fā)現(xiàn)新的圖不能存在包含新的邊的環(huán)。

將所有環(huán)縮點，新的圖是一個 DAG。

考慮新圖對應的 \(b\) 數(shù)量，記 \(deg_i\) 表示 \(i\) 的出度，則對應 \(b\) 數(shù)量為 \(\prod \limits_{i} deg_i!(n-deg_i-1)!\)。分別是 \(i\) 的喜愛排列中 \(a_i\) 前后的排列方案數(shù)。

這樣問題不弱于 DAG 計數(shù)，根據(jù) DAG 可以通過每次刪去入度為 \(0\) 的點最終變?yōu)榭請D，可以設計一個狀壓 DP，記 \(f_S\) 表示 \(S\) 子集生成的 DAG 排列對應的 \(b\) 數(shù)量之和，轉(zhuǎn)移考慮枚舉入度為 \(0\) 的點的一個子集然后子集反演，這樣復雜度為 \(O(3^c)\)，\(c\) 為 \(a\) 的環(huán)數(shù)量，無法通過。

進一步，考慮圖中存在很多長度相同的環(huán)，記狀態(tài) \((c_1,c_2,\cdots,c_n)\) 表示每種長度的環(huán)的個數(shù)，這樣狀態(tài)數(shù)不超過 \(1440\)，轉(zhuǎn)移直接枚舉 \(c'_i \leq c_i\) 的子集，算貢獻時要加一個組合數(shù)。

Submission Link.

Problem F. CF1530F Bingo

題意：

給定 \(n\) 和一個 \(n \times n\) 方陣 \(p_{1,1},p_{1,2},\cdots,p_{n,n}\)。考慮一個 \(n \times n\) 的 \(\texttt{01}\) 矩陣 \(a\)，\(a_{i,j}\) 有 \(p_{i,j}\) 的概率為 \(1\)，否則為 \(0\)。求至少存在一行或一列或主對角線或副對角線全為 \(1\) 的概率。答案對質(zhì)數(shù) \(31607\) 取模。

\(2 \leq n \leq 21\)，\(7\) 秒，\(512\) MB。

解法：

對角線并不特別，假設對角線是一個特殊的列。

首先變?yōu)榍竺恳恍辛信c對角線都存在 \(0\) 的概率。

直接容斥，我們可以得到一個時間復雜度不低于 \(O(2^{2n})\)，無法通過。

一個做法是直接 DP。記 \(f_{i,S}\) 表示前 \(i\) 行，不存在全為 \(1\) 的行，目前每列是否有 \(0\) 的二進制狀態(tài)為 \(S\)。可以發(fā)現(xiàn)轉(zhuǎn)移是或卷積形式，使用 FWT 可以在 \(O(2^nn^2)\) 復雜度內(nèi)解決此題，若想通過可能需要一些卡常手法。

另一個想法是，容斥做法復雜度瓶頸在于行列對角線總數(shù)較大，可以考慮僅對一部分容斥，比如列與對角線，對于另一部分，直接要求不存在為 \(1\) 的行。枚舉列與對角線的全 \(1\) 子集后，矩陣有些位置要求必為 \(1\)。然后枚舉每一行，第 \(i\) 行，可以算出這行中沒有要求的位置全都為 \(1\) 的概率乘積 \(p\)，顯然直接 \(ans \gets ans \times (1-p)\) 即可。直接做復雜度仍然是 \(O(2^nn^2)\)，預處理后即可做到 \(O(2^nn)\)。

Submission Link.