ZYStream

摘要： min-max 容斥 對于一個長度為 \(n\) 數列 \(\left \{ a_i \right \}\)，有如下式子： \[\max_{i=1}^{n} \left \{ a_i \right \}=\sum_{T \subseteq \left \{ 1,2,\cdots,n\right \} 閱讀全文

摘要： 題意 對于 \(n\) 個元素的任意排列 \(p\)，給定 \(k\) 和 \(m\)，初始變量 \(x=k\)，定義 \(f(k,m)\) 表示經過 \(m\) 次 \(x \gets p_x\) 變換后 \(x\) 的值，求所有 \(p\) 排列下的 \(x\) 的和對 \(998244353\ 閱讀全文

摘要： 引入 關于子集個數 關于 \(n\) 個元素的集合 \(U\) 的子集個數，有兩種理解方式。 組合數理解 從\(n\) 個元素的集合中能夠選擇構造出 \(\binom{n}{0}\) 個空集， $\binom{n}{1} $ 個元素個數為 $ 1$ 的集合，以此類推，子集個數即為\[\left | 閱讀全文

摘要： 條件限制 （1）棋盤的每一個小方格既可以染色（染成 C 種顏色中的一種），也可以不染色。 （2）棋盤的每一行至少有一個小方格被染色。 （3）棋盤的每一列至少有一個小方格被染色。 （4）每種顏色都在棋盤上出現至少一次。 題解 設全集為 \(U\) ，\(U\) 表示滿足條件（2）（3）的所有染色的方案 閱讀全文

摘要： 定義： 堆的底層數據結構是樹，一般不引起歧義的情況下，堆指的是二叉堆，其底層數據結構是完全二叉樹，堆分為大根堆和小根堆，大根堆的每個節點的父親都大于當前節點，小根堆反之，本文以小根堆為例 二叉堆插入 思路：將要插入的樹放在數組最后，令數組原來的大小為 \(size\) ，堆數組的名為 \(heap\ 閱讀全文

摘要： 定義： 將多個字符串以樹的方式存儲即為字典樹，如圖，\(1,4,3,12\) 表示 \(cca\) ，我么用 \(ch[i][j]\) 來表示第 \(i\) 個節點的 \(j\) 字符所指向的下一個節點，\(tag[u]\) 表示節點 \(u\) 是否代表一個字符串的結尾，如果是的話，\(tag[u 閱讀全文

摘要： 題目鏈接 [CSP-S 2024] 染色 題解 這是一道線性 \(dp\) 問題，難點在于在具體的題目背景中抽象出實際問題，最難的地方是分類討論。 根據題目的意思，如果第 \(i\) 位數字（\(a_{i}\)）的顏色和第 \(i\) 位之前的數字（\(a_{[1,i]}\)）的顏色都不同，則這個數 閱讀全文

摘要： 題目鏈接 [USACO06NOV] Corn Fields G 題解 這是一道典型的狀壓dp，對于 \(M\) 行 \(N\) 列的圖，由于每個點只有 \(1\) 和 \(0\) 兩種狀態，我們將其壓縮為一個長度為 \(M\) 的數組，數組（ \(g\) ）的每一項 \(g_{i}\) 表示狀態的二 閱讀全文