ws_zzy

摘要： Hall定理 二分圖 $X Y$，設 $|X| include include define lo (now 1; BuildTree(lo,l,mid); BuildTree(ro,mid+1,r); pushup(now); } void updataPoint(int now,int pla, 閱讀全文

摘要： 快速沃爾什變換學習筆記 (如果寫錯了請糾正)(表達不到位請多多包涵) $or$ 令$f[i][x]$表示第$i+1$位到第$n$位相同，第$1$位到第$i$位是$x$的子集的$a[y]$的和 于是FMT后的數(shù)組就是 $f[n][x]$ 考慮如何計算$f[i][x]$ 如果$x$的第$i$位是$0$， 閱讀全文

摘要： 最小樹形圖學習筆記 直接上代碼吧 include using namespace std; const int maxn=109; const int oo=1000000000; int n,m,r; int w[maxn][maxn]; int flag[maxn]; int pre[maxn] 閱讀全文

摘要： BZOJ 3027 [Ceoi2004]Sweet 生成函數(shù) 題解： 求出 $\le b$ 的答案減去 $ \le a 1$ 的答案 先寫出每個物品的生成函數(shù) $$ (1+x+x^{2}+x^{3} \cdots +x^{m_i})=\frac{1 x^{m_{i}+1}}{1 x} $$ 然后把他 閱讀全文

摘要： BZOJ 3456 城市規(guī)劃 Solution: 令$f(n)$表示n個點的無向簡單連通圖的個數(shù) $g(n)$表示n個點的無向簡單圖個數(shù) 那么有$g(n)=\sum_{i=1}^{n} \left(\begin{array}{c} n 1 \\ i 1 \end{array} \right) \ti 閱讀全文

摘要： 多項式除法 (參考Miskcoo's Space) $n$次多項式 A(x)，$m$次多項式 B(x)，要求出兩個多項式 $D(x)$，$R(x)$，滿足 $A(x)=D(x)B(x)+R(x)$ 并且$degD include include using namespace std; const 閱讀全文

摘要： 多項式求逆 求 $A(x)$ 在 $\%x^{n}$ 意義下的逆元 $B(x)$ 首先求出 $A(x)$ 在 $\%x^{\lceil \frac{n}{2} \rceil}$ 意義下的逆元 $C(x)$,即 $A(x)C(x)=1 $ $(\%x^{\lceil \frac{n}{2} \rcei 閱讀全文

摘要： 題解 算出所有的回文子序列減去連續(xù)的 先在中間插好* 用f[i]表示以i為對稱中心的對稱位置有多少對 位置i的貢獻為2f[i]-1 然后用manacher算不合法的 閱讀全文

摘要： 二維計算幾何 聲明： 由于本人較弱，并不能保證以下內容的100%正確 歡迎大佬來挑錯 基本定義 點積 叉積 基本運算 二維計算幾何常用算法 點在多邊形內的判定 二維凸包 注意 輸入不能有重復點 精度高時使用dcmp比較 旋轉卡殼求直徑 半平面交 O(n2) 半平面交注意判斷無解和無界 O(nlogn 閱讀全文

摘要： 三維計算幾何 聲明： 由于本人較弱，并不能保證以下內容的100%正確 歡迎大佬來挑錯 基本定義 半平面的表示 三維點積 應用：求夾角 求到平面的距離 求點在平面內的投影 直線和平面的交點 注意判斷分母為0 三維叉積 過不共線三點的平面的法向量 三角形的有向面積？？？？ 求出叉積后取長度 判斷點是否在 閱讀全文