FLYlai

摘要： 勢能線段樹包括了吉司機線段樹。思想就是正常線段樹可能遇到難 pushup 的情況，我們直接暴力遞歸，然后根據勢能分析說明這個暴力復雜度是均攤可接受的。 【勢能線段樹】 【例一】 CF438D The Child and Sequence 題意： 支持三種操作。 單點修改。 區間對給定數取模。 區間求 閱讀全文

摘要： 【基礎定義】 笛卡爾積。 \(A\times B=\{(a,b)|a\in A,b\in B\}\)。\(A\) 和 \(B\) 各是一個集合。 運算。一般研究二元運算（加減乘除等）。 運算是一種映射。從兩個集合 \(A,B\) 到一個集合 \(C\) 的映射，滿足 \(A\times B=C\)（ 閱讀全文

摘要： 集合冪級數 在 FMT 和 FWT 里有提到過。 對于一個序列 \(a_0\sim a_N\)，定義一個多元多項式 \(A(x_1\sim x_n)=\sum_{0\le I<2^{n}}a_I\cdot x_1^{i_1}x_2^{i_2}\cdots x_n^{i_n}\)，其中 \(i_1\s 閱讀全文

摘要： 【預備知識】 子集反演公式： \[f(S)=\sum_{T\subseteq S}g(T)\iff g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T) \]\[f(S)=\sum_{S\subseteq T}g(T)\iff g(S)=\sum_{S\subsete 閱讀全文

摘要： 楊表和 LIS、LDS、排列與序列等有緊密關系。 定義 設 \(x=(x_1,\dots,x_m)\) 是 \(n\) 的一個劃分。\(x_1\ge x_2\ge\cdots\ge x_m\)。 定義 1（楊圖）：一個 \(m\) 行的表格，第 \(i\) 行有 \(x_i\) 列（左對齊）。 定義 閱讀全文

摘要： 題意：給定序列，把序列分成 \(k\) 段，使每一段相同元素對數之和最小。\(n\le 10^5,k\le 20,a_i\le n\)。 容易寫出轉移方程：\(dp[i][j]=\min_{k=1}^{i}(dp[k-1][j-1]+w(k,i))\)，其中 \(w(k,i)\) 表示 \(a_k\ 閱讀全文

摘要： CF62E World Evil 遠古 2700。 給定 \(n\times m\) 網格圖，每條邊有容量。令第一列為源點，第 \(m\) 列為匯點，求最大流。\(n\le 5,m\le 10^5\)。 最大流轉最小割，然后狀壓 DP 即可。\(dp[i][S]\) 表示前 \(i\) 列阻斷了 \ 閱讀全文

摘要： 紀念一下場切 5 題。 A 給定序列 \(a\)，一次操作可選 \(k\) 個數，同時減去它們的按位與。問有多少個 \(k\) 能把 \(a\) 全消為 \(0\)。\(n\le 10^5\)。 對于一個位，\(1\) 的個數的變化量必為 \(k\) 的倍數。所以 \(k\) 要是每一位 \(1\) 閱讀全文

摘要： 抽象代數前置 【Burnside 引理】 問題引入 涂色 \(2\times 2\) 的方格。旋轉相同算一種。有多少種本質不同染色方案？ 可以數出有 \(6\) 種。 以此為例介紹 Burnside 引理。 設一種染色方案為 \(x\)，\(g_{a}\) 為一種變換，表示將某種染色方案順時針旋轉 閱讀全文