Jason Fan.

题意 定义一个长度为 nnn 的序列 AAA 的最大前缀和 maxpre(1,n)\mathrm{maxpre}(1,n)maxpre(1,n) 为 max⁡i=1nsumi\max_{i=1}^{n}sum_imaxi=1n​sumi​ ，其中 sumi=∑i=1nAisum_i = \sum_{i=1}^n A_isumi​=∑i=1n​Ai​ 现给你长度为 nnn 的序列 aaa，以及 mmm 个询问 qqq ，每次给出 l,rl,rl,r ，让你求出 ∑i=lr∑j=irmaxpre(i,j)\sum_{i=l}^{r}\sum_{j=i}^{r} \mathrm{maxpre}(i,j)∑i=lr​∑j=ir​maxpre(i,j) 强制在线， n≤2×106,q≤107n\leq 2\times 10^6,q\leq 10^7n≤2×106,q≤107 题解 把 maxpre(l,r)\mathrm{maxpre}(l,r)maxpre(l,r) 拆开来看，那么 maxpre(l,r)=max⁡i=lrsumi−suml−1\mathrm{maxpre}(l,r) = \ ...

fdbc2997623a61cf73a7235ddd759531c5c1d64aa56d5f2b54a26e0ff5aca40435936bfac755d0e80d47276d76b38467a49f75f78fb7502daff6430dbd3f32376a19774d295d1503726ce3e5b92d6af360eb141906cef96a533f9e1ad5e23577df75928cd6419319a1ba2cd7e39b4fcde6496e0b516c5b294ee61477eedee50fa7e5b1a182f598ba8eea5ee2f2e254bbb5f131878f9a818e784c0953b95533d50c289476fb25eb5355b259c59d944c15b6a28df0031aa18572ace88c35767a246a7c8ce83c7802a17ae5701be9c27fed286d84452da926ea16c4de123768c1919dd3d37b77a285a748cb186aa71f02bb27833e9ce8591ef30 ...

fdbc2997623a61cf73a7235ddd75953112e86bf09457d59c43cbf7536c84a30620b4617a571029c342e2ca06503345dabc4c2333ee51f962d80fbc3b485c2bdbcbed0175739263386aadec60a74d0e4d274a562aeed8eddc513932bb8eab3db67592b21a95172ec4ce0a783eed6e244fb2abd63f11ee089db4c0f41bef977c46bd8c3030a80745a6604f1775d15fc85f9c4e70afaaa78d6845c8da6058bf0177be3c0681de2009023fef57d850a479c7ff68d35eed6b1c1d2b515e82ecfb60be26ffa9cc03ba8fba8df5119c14e567b873feae595c3eb9f74a63ec2eed6a2013a12b9e4e6008aad3a5a9e3ad57b0663e9fbc288cb90825c6b ...

在非线形时间内筛某些奇性函数前缀和 狄利克雷卷积 (f∗g)(n)=∑d∣nf(d)g(nd)(f\ast g)(n)=\sum_{d\mid n} f(d)g(\tfrac{n}{d}) (f∗g)(n)=d∣n∑​f(d)g(dn​) 一些结论，会用到（ 注: I(n)=1,id(n)=n,ϵ(n)=[n=1]I(n)=1,id(n)=n,\epsilon(n)=[n=1]I(n)=1,id(n)=n,ϵ(n)=[n=1] ） φ∗I=idμ∗I=ϵμ∗id=φ\begin{aligned} \varphi \ast I=id\\ \mu \ast I=\epsilon\\ \mu \ast id=\varphi \end{aligned} φ∗I=idμ∗I=ϵμ∗id=φ​ 线性筛 φ,μ\varphi,\muφ,μ 12345678910111213141516171819const int N = 100000;int p[N],tot;ll phi[N],mu[N];bool v[N];void init(int n) { for(int i=2;i&l ...

题意 给一颗 nnn 个点的内向基环树，每个点的出度为一，每个点可染 mmm 种颜色，求本质不同的染色方案数。 mod 109+7\bmod 10^9+7mod109+7 m≤109,3≤n≤105m\le 10^9,3\le n\le 10^5 m≤109,3≤n≤105 题解 基环树一个重要的特征是环，考虑先算出环上每个点对应子树的染色方案数。 其中要判断两颗子树是否同构，需要树哈希： 按照 dfs 序可以将树上结点对应到序列上，在序列上填上对应结点的深度，如上图得到序列为: 12333232\begin{array}{c} 1&2&3&3&3&2&3&2 \end{array} 1​2​3​3​3​2​3​2​ 显然，根据序列可以还原出形态唯一的树。那么树哈希便转换成了序列上的哈希。具体的，需要递归处理，记 hash(u)hash(u)hash(u) 为 uuu 子树的哈希值，初始 hash(u)=depuhash(u)=dep_uhash(u)=depu​ ，插入 vvv 子树，就相当于两个序列接起来，hash(u)′ ...

ZJOI2014力 题意 给出 nnn 个数 q1,q2,…qnq_1,q_2, \dots q_nq1​,q2​,…qn​ ，定义 Fj=∑i=1j−1qi×qj(i−j)2−∑i=j+1nqi×qj(i−j)2F_j=\sum_{i=1}^{j-1} \frac{q_i\times q_j}{(i-j)^2} - \sum_{i=j+1}^n \frac{q_i\times q_j}{(i-j)^2} Fj​=i=1∑j−1​(i−j)2qi​×qj​​−i=j+1∑n​(i−j)2qi​×qj​​ Ei=FiqiE_i=\frac{F_i}{q_i} Ei​=qi​Fi​​ 对于 1≤i≤n1\le i\le n1≤i≤n ，求 EiE_iEi​ 的值。1≤n≤105,0<qi<1091\le n \le 10^5 ,0\lt q_i \lt 10^91≤n≤105,0<qi​<109 . 题解 Ej=∑i=1j−1qi(i−j)2−∑i=j+1nqi(i−j)2Ej=∑i=0jqi(i−j)2−∑i=jnqi(i−j)2E_j=\sum_{i=1}^ ...

网络流最小割相关 最小割等于最大流，最小割可以用最大流求的，那么重点在于如何建模，将要求的东西转换为最小割。 最小割求方案 随便输出一种方案只要在残量网络上从源点 BFS ，能到的点在 SSS 集合中，不能到的点在 TTT 集合中，∀(u,v),u∈S,v∈T\forall (u,v),u\in S ,v\in T∀(u,v),u∈S,v∈T 且 u,vu,vu,v 满流则该边属于最小割集。 最小割可行边 就是在某个最小割集中出现的边，设边 (u,v)(u,v)(u,v) ，其为可行边的充要条件： 该边满流 。 残量网络上不存在 uuu 到 vvv 的增广路。 若不满流显然可以找到另一条更小的满流的限制流量的边。 若满流但在残余网络中能找到入点到出点的路径，那么需要同时割掉这条边和残余网络中路径上某条边才能实现“割”，而这两条边上的流量和一定等于其他某条或某几条满流的边的流量和，否则可以继续增广，又因为位于残余网络上的那条边一定不满流，所以这种割法不是最小割。 判断一条边是否可行直接 BFS 即可，单次 O(n)O(n)O(n) 如果在同一个图上大量判断，可以用 tarjan ...

LOJ - 2196 题意 给定长度为 NNN 序列 AAA ，序列中的每一项 AiA_iAi​ 有删除代价 BiB_iBi​ 和附加属性 CiC_iCi​。 请删除若干项，使得 AAA 的最长上升子序列长度减少至少 111，且付出的代价之和最小，并输出方案。如果有多种方案，请输出将删去项的附加属性排序之后，字典序最小的一种。 N≤700N\le 700 N≤700 题解 求 LIS 跑一遍 DP 即可，记最大的 DP 值为 mxdpmxdpmxdp ，从 DP 值等于 mxdpmxdpmxdp 的位置倒推回去，按转移关系建边得到一个转移图，显然入度为零的都是 DP 值为一的，出度为零的都是 DP 值为 mxdpmxdpmxdp 的。现在就是要求最小的代价使入度为零的点与出度为 mxdpmxdpmxdp 的点不连通。 那不就是最小割吗。具体建图： 超级源点 SSS 连向所有 DP 值为零的点，边权 +∞+\infty+∞ 所有 DP 值为 mxdpmxdpmxdp 的点连向超级汇点 TTT 边权 +∞+\infty+∞ 对于所有 dp[u]+1=dp[v],u<v,Au&l ...

fdbc2997623a61cf73a7235ddd759531940afb38b42975cb2bd1b7273226e7a6f4491464e6b8f8de1e2939658e3cf4d300236242fe0f55101316d2a1950ad391b97c88c6fb19b68d9d11c38538ae787c9def02eac9fa328554861f011cdefaa5b05455f6dd8efd44377db163a393bec5b812793909012d0228db932fccff5fc6ea5881ea8198a7ecdb8800e0f5e0e2b079c62fef41b506de6b46ecf14523de52eb30719d11df393fa3dd00525ef99890c15d2f762b4f95a56fdf8eb01df9793dc2a4bd7b9659f1e308fc33b0b21bbccc16b82489697f9b4ae8782766f058f8afb7b8c1f37a5669a545762472bc0ebaa5c5b3da9c2df6821cd ...

fdbc2997623a61cf73a7235ddd759531940afb38b42975cb2bd1b7273226e7a6f4491464e6b8f8de1e2939658e3cf4d34b7510dc8943b5b2f3323eacdc2e2b8330e0d19dd9da4e20bdf3effe1b4dc5bd9300d950a002f558865a19e0610940735459f51254260ac1e14e3da7dfb3e86c71f3c00a4f4fdc0980e2f7defe85743b19e27ee622b1652b22a548c36f4dd4a8b70a892550ecd4ac8bb8d5c3f2b10c1ff8aa425d4c93041bd1d4c1de406eed91566dcd65564f479dd2526ea8fca3cca6c54b00d1cae76a7453753d96c577a6f08b24cdf4a4c025781f1c400094d906ff326a832ca6a3cb854a81c61138bdb82a9cca61350caa6d6f7 ...