4 Lynstery

尚未进行身份认证

我要认证

一只蒟蒻

等级
TA的排名 1w+

博客搬家..

https://lynstery.coding.me/

2018-03-18 20:34:28

[最小割] BZOJ3144: [Hnoi2013]切糕

经典的最小割建图,用 ∞∞\infty 边体现限制条件。inline char gc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline int getint(){ ...

2018-02-21 22:26:54

[最小割+Tarjan] BZOJ1797: [Ahoi2009]Mincut 最小割

关于最小割唯一性:在残余网络上跑 TarjanTarjanTarjan 。记 idxidxid_x为点 xxx 所在 SCCSCCSCC 的编号。将每个 SCCSCCSCC 缩成一个点,得到的新图就只含有满流边了。那么新图的任一 S−TS−TS-T 割都对应原图的某个最小割。对于任意一条满流边 (u,v)(u,v)(u,v),若能够出现在某个最小割集中,当且仅当 idu≠idvidu≠...

2018-02-21 21:47:30

《最小割模型在信息学竞赛中的应用》——学习笔记

《最小割模型在信息学竞赛中的应用》学习笔记基础流网络的定义,容量限制,反对称性,流守恒性…我们约定对于点集X,YX,YX,Y ,令 f(X,Y)=∑u∈X∑v∈Yf(u,v)f(X,Y)=∑u∈X∑v∈Yf(u,v)f(X,Y)=\sum_{u \in X}\sum_{v \in Y} f(u,v) ∀X,f(X,X)=0∀X,Y,f(X,Y)=−f(Y,X)∀X,Y,Z,&nb...

2018-02-16 00:44:50

[最小割] BZOJ2400: Optimal Marks

论文题。 二进制每位独立算,每个编号就只有 010101 两种。可以看作分成两个集合,用最小割模型解。 题目要求在边权和最小的前提下,还要保证编号和最小。这个只需要每次从 TTT 出发倒着走,能到的点一定是在 TTT 集合内,其他的都看作是 000,这样就是最小的。#include<cstdio>#include<cctype>#include<cst...

2018-02-14 23:39:21

[Matrix-Tree 定理] SPOJ HIGH - Highways

模板题。Matrix−TreeMatrix−TreeMatrix-Tree 定理用于求生成树个数。给出一个无向图 GGG ,GGG 的度数矩阵 DDD 是一个 n∗nn∗nn∗n 的矩阵,当 i≠ji≠ji \neq j 时, di,j=0di,j=0d_{i,j}=0 ,di,idi,id_{i,i} 等于 iii 的度数。GGG 的邻接矩阵为 AAA 。我们定义 GGG 的 Kir...

2018-02-13 21:34:38

[二进制分组 + 凸包] BZOJ4140: 共点圆加强版

对于给出的一个圆心 (xi,yi)(xi,yi)(x_i,y_i) ,在它内部点 (x,y)(x,y)(x,y) 需满足 (x−xi)2+(y−yi)2≤x2i+y2i⇔x2+y2≤2xxi+2yyi⇔yi≥−xyxi+x2+y22y(x−xi)2+(y−yi)2≤xi2+yi2⇔x2+y2≤2xxi+2yyi⇔yi≥−xyxi+x2+y22y(x-x_i)^2+(y-y_i)^2 \le x...

2018-02-11 23:47:36

斯特林数(Stirling)——学习笔记

第一类斯特林数s(n,m)s(n,m)s(n,m) 表示 nnn 个元素组成 mmm 个圆排列 有 s(n,m)=s(n−1,m−1)+s(n−1,m)∗(n−1)s(n,m)=s(n−1,m−1)+s(n−1,m)∗(n−1)s(n,m)=s(n−1,m−1)+s(n−1,m)∗(n−1)s(n,m)=∑i=1ns(n−i,m−1)(n−1i−1)(i−1)!s(n,m)=...

2018-02-11 20:30:25

伯努利数(Bernoulli)——学习笔记

http://www.bernoulli.org/ http://blog.csdn.net/whai362/article/details/43148939 https://baike.baidu.com/item/%E4%BC%AF%E5%8A%AA%E5%88%A9%E6%95%B0/1304247?fr=aladdin https://www.cnblogs.com...

2018-02-10 22:21:54

[分治FFT] HDU5730 Shell Necklace

分治 FFTFFTFFT,就是 CDQCDQCDQ 分治加 FFTFFTFFT。 用来解决这样的问题:已知 g(x)g(x)g(x),且 f(i)=∑i=0n−1f(i)g(n−i)f(i)=∑i=0n−1f(i)g(n−i)f(i)=\sum_{i=0}^{n-1} f(i)g(n-i) 求 f(x)f(x)f(x)。 就是直接 CDQCDQCDQ 分治,算 [L,mid][L,mi...

2018-02-09 23:25:52

[原根 + NTT] LOJ#2183 BZOJ3992:「SDOI2015」序列统计

做法比较显然,应该就是这样的 DPDPDP : f(i)=∑j∗k≡i(modm)f′(j)g(k)f(i)=∑j∗k≡i(modm)f′(j)g(k) f(i)=\sum_{j*k \equiv i \pmod m} f'(j)g(k) 可以用原根转化为加法,就变成 f(i)=∑j+k≡i(modm)f′(j)g(k)f(i)=∑j+k≡i(modm)f′(j)g(k)f(i)=\...

2018-02-09 15:42:33

快速数论变换(NTT)——学习笔记

NTT嗷, 很简单。FFTFFTFFT 之所以能加速,是由于有主n次单位根 wn=e2πinwn=e2πinw_n=e^{\frac{2\pi i}{n}} ,的那些很好的性质。而在自然数域,模 PPP 意义下,可以把 wnwnw_n 换成 gP−1ngP−1ng^{\frac{P-1}{n}} ,ggg 是 PPP 的原根,可以发现那些性质是类似的。逆变换也是把 gP−1ngP−1ng...

2018-02-08 21:30:20

多项式求逆——学习笔记

基本概念多项式的度:对于一个多项式 A(x)A(x)A(x) ,称其最高项次数为多项式的度,记作 degAdegAdeg A 多项式的逆元:对于 A(x)A(x)A(x) 若存在 B(x)B(x)B(x) 满足 degB≤degAdegB≤degAdegB \le degA 且 A(x)B(x)≡1(modxn)A(x)B(x)≡1(modxn) A(x)B(x) \equiv 1...

2018-02-08 18:56:03

【施工ing】生成函数与多项式——学习笔记

生成函数大概是一个无穷幂级数形式的函数,我们只关心它的形式,而不会去带入 xx 求值。可以看做是多项式,只是带入没有意义。它的一些运算可以对应组合意义,所以能通过它解决一些组合问题。一般生成函数(OGF):f(x)=a0+a1x1+a2x2+a3x3+a4x4...f(x)=a_0+a_1x^1+a_2x^2+a_3x^3+a_4x^4...指数型生成函数(EGF),之后会看到为什么要

2018-01-18 21:16:11

Emacs 配置

记一下…(custom-set-variables ;; custom-set-variables was added by Custom. ;; If you edit it by hand, you could mess it up, so be careful. ;; Your init file should contain only one such instance.

2017-12-29 10:32:56

[线性基] BZOJ2844: albus就是要第一个出场

有个结论:一个可异或得到的数,用原来 nn 个数异或得到它都有 2n−cnt2^{n-cnt} 种组合方法。想想发现是很有道理的,就是不要把消出的 n−cntn-cnt 扔掉,00 怎么异或都不变的,所以是 2n−cnt2^{n-cnt}。 知道这个就做完了。#include<cstdio>#include<algorithm>using namespace std;const int MO

2017-12-24 21:20:10

[DFS树 + 线性基] BZOJ2115: [Wc2011] Xor

线性基裸题。需要知道一个东西:对于随意一条 11 到 nn 的路径的异或和,都可以通过任意一条 11 到 nn 路径的异或和与图中的一些环的异或和来组合得到。 然后就 DFSDFS 树找简单环,瞎搞搞…#include<cstdio>#include<algorithm>using namespace std;const int maxn=50005,maxe=200005;typedef

2017-12-24 19:30:12

[线性基] HDU3949: XOR

裸题。线性基消成对角后, 最高位为 i 的数是唯一的。这个性质很好,使得选的数集中最大数的最高位,在异或后一定是 11。设 bib_i 为线性基第 ii 小的数,kik_i 为二进制下第 ii 位。 答案就是 Xor b[i]ki \text{Xor } b[i]k_i。#include<cstdio>#include<cstring>#include<algorithm>using nam

2017-12-24 18:53:18

线性基——学习笔记

http://blog.csdn.net/qaq__qaq/article/details/53812883 https://blog.sengxian.com/algorithms/linear-basis https://www.cnblogs.com/vb4896/p/6149022.html 一些线代前置知识: 向量空间 \quad 定义 (F,V,+,⋅)(F, V, +, \c

2017-12-19 21:20:21

[WQS二分套WQS二分] Codeforces #739E. Gosha is hunting

O(n3)O(n^3) DPDP 很显然。要优化就只能 WQSWQS 二分了。每种食物肯定是都用完的,所以相当于强制选若干个 AA 物品,若干个 BB 物品。发现物品选越多,收益是会增加的越来越慢的,所以这两维都可以 WQSWQS 二分。就能做到 O(nlog2n)O(nlog^2 n) ,很优美。 http://codeforces.com/blog/entry/49691 #include<c

2017-12-19 19:12:39

查看更多

勋章 我的勋章
  • 专栏达人
    专栏达人
    授予成功创建个人博客专栏的用户。专栏中添加五篇以上博文即可点亮!撰写博客专栏浓缩技术精华,专栏达人就是你!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!