glq_C

摘要： 網絡流建模思路 想辦法讓一個流或一組割代表一種方案。 無源匯上下界可行流 先令每條邊的流量為它的下界，此時每個點可能不滿足流量守恒。對每個點求出它的凈流量：即流入減流出。 有源匯上下界可行流 集合劃分模型 假設有若干個元素，每個元素要么放到A，要么放到B。每個元素放到A/B有相應的代價，還有形如“若 閱讀全文

摘要： $$F[k]=\sum_{i=0}^{n-1}(\omega_n^k)^iG[i]\iff G[k]=\frac{1}{n}\sum_{i=0}^{n-1}(\omega_n^{-k})^iF[i]$$ 首先根據單位根反演，問題可以轉化為對于一個多項式帶入$N$個單位根求值。 形式化地說：給定$F( 閱讀全文

摘要： 定義 對一個數的集合$S$，其線性基就是由最少的數構成的集合$B$，滿足在$S$中任選一些數異或后的值，都可以在$B$中選一些數異或使得兩個值相等。 性質 $B$中任意元素異或起來結果不為$0$ ps：即要求$B$中元素線性無關，否則一定可以刪掉至少一個數，使得$B$能表示的數集不變。 為了方便，我 閱讀全文

摘要： P8631 [藍橋杯 2015 國 AC] 切開字符串 Sol 首先問題可以轉化為對每個前綴求出本質不同奇回文子串數，和對每個后綴求出本質不同子串數和本質不同奇回文子串數。 本質不同子串數 對每個后綴求出本質不同子串數，考慮后綴數組。對于從位置$i$開始的后綴，這個后綴的本質不同子串數即為把$i,i 閱讀全文

摘要： 插數dp （名字是我口胡的，因為它直觀上看就在做插數這件事） 假設有一個給定的排列，初始我們有一個空序列，現在從小到大往這個空序列中插入1~n，使得最后得到的序列恰為給定的排列 在插入的過程中我們可以把當前得到的序列想象成若干段，每一段就表示這一段是一個連續的整體，以后插數不能在往里插了；同時我們欽 閱讀全文

摘要： 階 稱最小的正整數$k$，使得$a^k\equiv 1\pmod m$為$a$在膜$m$意義下的階。 $a$在膜$m$意義下有階的充要條件是$gcd(a,m)=1$,必要性由裴蜀定理得出，充分性由歐拉定理給出 階可以通俗的理解為膜意義下冪的最小循環節，根據歐拉定理，這個上界是$\phi(m)$ 原根 閱讀全文

摘要： 第二類斯特林數 組合意義： 將n個有標號物品劃分為m個無標號的非空集合的方案數，記為$n\brace m$ 遞推式 $$ \begin{aligned}{0 \brace 0}&=1\ {n \brace 0}&=0 \quad(n>0)\ {n \brace m}&={n-1 \brace m-1 閱讀全文

摘要： 先對反演和一些簡單的應用總結一些吧，更高的東西聯賽前來不及搞了（悲） 二項式反演 概要 二項式反演可以看作是一種特殊的子集反演，特殊之處在于一個集合的價值只與這個集合的大小有關。 $f(n)=\sum\limits_{i=0}^n (-1)^i\dbinom{n}{i} g(i) \iff g(n) 閱讀全文

摘要： 眾所周知，三分可以求單峰函數極值 那么首先要明確單峰函數的定義：它們有唯一的極大值點，在極大值左側嚴格單調上升，右側嚴格單調下降（單谷函數相反） ###注意 單峰函數并不一定是凸函數，凸函數要求斜率單調，或者說差分（導數）單調。 而且除了不一定滿足“有唯一的極大值點”這個條件，凸函數一定是單峰函數（ 閱讀全文

摘要： 模板 ###條件 無向圖存在歐拉回路的充要條件是任意一個點的度數都為偶數，且所有的邊是聯通的（也就是除去孤立點外，圖是連通的） 有向圖存在歐拉回路的充要條件是任意一個點的入度等于其出度，且忽略邊的方向后，邊是連通的（同上，等價于除去孤立點外，圖是連通的） 無向圖存在歐拉路徑的充要條件是有且僅有兩個點 閱讀全文