P6076 [JSOI2015]染色问题 题解
个人认为是道很好的组合加容斥练习题。 Solution 考虑将行，列，颜色的限制分开处理。 先限制颜色。 令 $f(i)$ 为只使用 $i$ 种颜色，满足行列限制的方案数， $$ ans=\sum\limits_{i=0}^c\dbinom{c}{i}(-1)^{c-i}f(i) $$ 再限制列。 令 $g(i,j)$ 为只是用 $i$ 种颜色，只填 $j$ 列的方案数。 $$ f(i)=\sum\limits_{j=0}^m\dbinom{m}{j}(-1)^{c-j}g(i,j) $$ 最后 $$ g(i,j)=((i+1)^j-1)^n $$ 带入求解即可，时间复杂度 $O(mc\log n)$ 。 Code #include<bits/stdc++.h> #defi..
P7044 「MCOI-03」括号 题解
很有意思的组合计数加容斥。 Solution $K=0$ 就是经典括号匹配问题，开个栈模拟一下即可。 $K=1$ 显然可以 $O(n^2)$ 枚举子串，但这样复杂度太高。 考虑拆开找贡献，对于下标为 $i$ 的左括号，设它匹配的右括号下标为 $j$ (特别的，没有匹配时 $j=n+1$ )。 那么易证，这个左括号对所有 $i\le r＜ j$ 且 $1\le l\le i$ 的区间都有 1 的贡献，总贡献即为 $i\times(j-i)$ 。 右括号同理，因此可以 $O(n)$ 计算。 $K>1$ 套用 $K=1$ 时的计算方法，找贡献。 我们发现对于一个 $K$ 级偏值的字符串，只会对包含它的母串的 $K+1$ 级偏值造成贡献。 还是假设以下一个下标为 $i$ 的左括号，..
P3380 【模板】二逼平衡树（树套树）题解
萌新怒码4k ，搞出来一份不开O2就会T的代码。 只会 fhq-treap ，所以就来了一发 线段树套 fhq-treap。 也就调了一个小时 一些注意点 调用 fhq-treap 时 root 要传址。 寻找排名为 k 的数的时候二分的 check 要 queryrk(k+1) ，因为 queryrk() 找的是小于 k 的数，而 check 的要求是小于等于 k 的数。 Code #include<bits/stdc++.h> #define N 100005 #define orz puts("orzwyy332623");//tiaoshi #define ls(p) p<<1 #define rs(p) p<<1|1 using ..
多项式入门
前言 这个傻狗啥都不会还敢来学多项式。 虽然这好像连入门都不算（（（ 背板！！！背板！！！ 前置的一些定义 点值表示法：将 $n+1$ 个不同的值带入到 $n$ 次多项式中形成 $n+1$ 个点的坐标以代表唯一多项式，支持 $O(n)$ 计算卷积。 单位根：复数意义下 $x^{n}=1$ 即为 $n$ 次单位根。(有 $n$ 个) 本原单位根：$e^{i\frac{2\pi}{n}}$ 称为 $n$ 次单位根的本原单位根，记为 $ω_n$ 。 原根：若 $1\le g\le n-1$ 且 $g$ 模 $n$ 的阶为 $\varphi(n)$ ，则称 $g$ 为 $n$ 的原根。 卷积的一般形式： $$ c_i=\sum\limits_{i=j\oplus k}a_jb_k $$ DFT ..
点分治学习笔记
定义 点分治，顾名思义，就是通过基于点的分治的一种算法。 通常用于处理树上问题，如树上所有路径统计。 我们设一次操作的时间复杂度为 $O(1)$ ，那么一次点分治复杂度为 $O(n \log n)$ 。 具体流程 操作->分治->操作……（不知道怎么讲） 点分治的核心主要在于高效的分治，每一次都可以将所求区间大小缩短至 $\dfrac{1}{k}$ 。 因此 $T(n)=k\times T(n/k)$ ，根据主定理，时间复杂度为 $O(n \log n)$ 。 分治的关键在于从在每一次操作的树上寻找重心，易证以重心为根的每颗子树大小不超过 $\dfrac{n}{2}$ ，从而可以有效缩小操作区间，保证正确的复杂度。(其实感性也很好理解的来着) 例题 P3806 【模板】点分治1 ..
CF1661D Progressions Covering 题解
link 简化题意 给定一个长度为 $n$ 的数组 $A$ ，和一种操作。 每次操作选定长度为 $k$ 的区间 $[L,R]$ , 将 $A_L-1$，$A_{L+1}-2$ …… $A_R-k$ 。 求使 $A$ 中所有元素小于等于0所需的最小操作个数。 Sulution 一个显然的贪心思路： 从后往前枚举，对于每个大于等于1的 $A_i$，将区间 $[i-k+1,k]$ 操作 $\left\lfloor\dfrac{A_i}{k}\right\rfloor$ 次。 证明略。 暴力实现是 $O(n^2)$ 的，我们考虑维护这个操作。 因为需要区间修改，单点查询，考虑线段树，但是每次修改的值不一定，考虑转化。 发现每次修改对于区间的差分数组改变一致，于是将原数组转化为差分数组。 那么我们..
P5289 皮配 题解
（注 ：第一次打这种超出目前能力的 dp ，调了四个晚上。 简化题意： 有四位导师，他们被两两一组分成了红 / 蓝阵营，另外两两一组分成了鸭 / R 派系 有 $n$ 所**学校**，来自 $c$ 个**城市**，第 $i$ 个学校有 $s_i$ 名选手。 同一所学校的选手必须选择同一个导师。同一个城市的选手必须选择同一个阵营。同城对派系的选择没有限制。 有 $k$ 所学校的选手有自己讨厌的老师。 求一共有多少种情况，答案对 $998244353$ 取模。 (注：每个学校可以加入自己讨厌的老师的阵营/派系) 50 pts 做法： 设 dp 状态为 $f_{(0/1,i,j,k)}$，表示 dp 到第 $i$ 个学校，选择 蓝(0)/红(1) 阵营，蓝阵营有 $j..
欧拉函数小结
定义 $\varphi(x)$ 指对于 $\forall i\in [1,x]$ ，满足 $\gcd(i,x)=1$ 的 $i$ 的个数。 也就是小于等于 $x$ 的正整数中与其互质的数的个数。 基本推论 $\varphi(x)=x-1\quad(x\in \mathbb{P})$ $ \begin{aligned} \varphi(p^k)& =p^k-p^{k-1} \quad(p\in \mathbb{P},k\in \Z^*) \\ &= p^k(1-\frac{1}{p})\quad(p\in \mathbb{P},k\in \Z^*)\end{aligned}$ 这是因为只有当一个数不包含质数 $p$ ，才可能与 $x$ 互质。而包含质数 $p$ 的数一共有$ p^{k-1} $个，即 ..
P2572 [SCOI2010]序列操作 题解
线段树全家桶，还是挺考验码力的。 注意点： 三种 tag 的覆盖关系（隔壁调了半年） push_up 和 push_down 的更新细节 query2 的去最值细节（我举得我的方法蛮好的）。 总之坑点还是蛮多的。 code #include<bits/stdc++.h> #define N 200005 #define ls(p) p<<1 #define rs(p) p<<1|1 using namespace std; int read(){ int x=0,w=1; char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=get..
模拟退火学习笔记
模拟退火，RP检测器，玄学算法，yyds。 看什么学习笔记，当然是看日报了。 过程 就是模拟冶金学的退火过程，乱搞，具体理论的证明我也不是很懂。 流程图(自己懂就好)： 优化/乱搞 温度T的初始值设置问题。 温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。 退火速度问题。 模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索(退火)是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。