1、小蜘蛛
题目描述
zty 一共养了 n 只小蜘蛛，第 i 只小蜘蛛有一个编号Ai ，这n 只小蜘蛛的编号恰好构成了一个长度为 n 的排列。小蜘蛛们在交友时总喜欢站成一排。他们的交友方式也很特别，每只小蜘蛛只会主动和在自己左方，且离自己最近的编号比自己小的小蜘蛛成为好朋友。若不存在，则不会主动结交好友。注意：这种好朋友关系是双向的，即若 A 主动结交 B 为好友，则 A、B 会互为好朋友。而这种交友方式是具有传递性的，即若 B 和 A 是好朋友，B 和 C 是好朋友，那么 A 和C 也是好朋友。
在交友结束后，每只小蜘蛛都只和好朋友们玩耍。因此在玩耍时，小蜘蛛们会分成不同的群体，互为好朋友的蜘蛛们会分成一个群体。显然，若两只蜘蛛在互为好朋友，则他们一定在一个群体。否则，他们一定不在同一个群体。
可是这样会给 zty 带来管理上的麻烦。一种交友时的排列顺序给zty 带来的麻烦度为: 小蜘蛛们交友后分成的不同的群体的个数的 k 次方。zty 想知道，对于所有交友时的排列，麻烦度的总和是多少。你只需要告诉 zty 麻烦度的总和对998244353取模的结果。
数据范围：\(1 \le n \le 10^5 , 0 \le k \le 20\)
解法
枚举排列不可行，考虑枚举每个群体在最后答案中的总贡献。
考虑 \(k=1\) 时。设 \(f[i]\)表示长度为 \(i\) 的排列的答案，考虑如何从 \(f[i-1]\)转移到 \(f[i]\)
从 \(f[i-1]\)转移到 \(f[i]\)，考虑在 \(1\) ~ \(i-1\) 的排列中，插入元素 \(i\)，此时 \(i\) 为该排列的最大元素。若将 \(i\) 放在排列的第一个，则会单独形成一个团体，对答案的贡献为\((n-1)!\)
若将 \(i\) 放在排列的其他位置，则其左面必然会有比他小的元素，即其必然会和其他元素形成一个团体。除第一个位置外，一共有 \(i\) 个位置可以插入，对答案的贡献为\(i*f[i-1]\)
故 \(f[i]=(n-1)!+i*f[i-1]\)
先想想 \(k=2\) 时，设 \(f[i]\)表示 \(k=2\) 时答案，想想怎么从 \(f[i-1]\)转移到\(f[i]\)。
在 DP 中，第二种（不在首端）时，\(i\) 加入对团体数量贡献仍为\(i*f[i-1]\)。
在第一种（在首端）时，对于每个排列，其形成的团体数量\(+1\)。设原来有 \(x\) 个团体，加入 \(i\) 后，有 \(x+1\) 个。则对于该排列，答案变化为\((x+1)^2-x ^2=2x+1\)。所以只需再原答案的基础上，加入 \(2x+1\) 的贡献即可。
在 \(k=1\) 时，其贡献 \(x\) 已经求出，加入即可
\(k=3\) 时，有\((x+1)^3-x^3=3x^2+3x+1\)，同理加入维护即可
本质是二项式定理的应用。
设 \(f[i][j]\)为 \( k=i\) 时 \(1\)~\(j\) 排列的答案。
有 \(f[i][j]=j*f[i][j-1]+\sum^{k-1}_{p=0}\binom k p f[p][i-1]\)
预处理组合数时间复杂度 \(O(nk^2)\)，期望得分：100 分。
反思
对于排列型DP常考虑插入法，因为排序一定是插入1n，而插入第i个数时排列里只有1i-1，对于i插入至某个位置，则此时i的贡献很明显，易写出方程（例如求逆序对有k个的n个数的排列数）
因此找枚举对象是DP中最难的一环
\(p.s.\)注意 \(k=0\) 的特判
2、[P1868] 饥饿的奶牛
题目描述
有 \(N\) 个区间，每个区间 \(x,y\) 表示提供的 \(x\sim y\) 共 \(y-x+1\) 堆优质牧草。你可以选择任意区间但不能有重复的部分。求最多能吃到的牧草堆数。
\(1 \leq n \leq 1.5 \times 10^5\)，\(0 \leq x \leq y \leq 3 \times 10^6\)。
解法
看数据范围，可以设计出两种dp
1、状态为区间，不能保证左右端点同时有序，在右端点排序后用二分查找更新（没想到二分qwq）
2、状态为下标，找对应区间往回取即可，用vector或邻接表存储下标对应区间
3、组合
[P8594] 一个仇的复
P5665 [CSP-S2019] 划分
朴素方程（\(O(n^3)\)以及优化后的\(O(n^2)\)）略
易看出一个贪心：每次取的最后一段越短越好（考场上建议打表验证）
故转移点\(j\)为满足\(s[i]-s[j] \ge s[j]-s[pre[j]]\)的最大的\(j\)
移项：\(s[i] \ge s[j]*2-s[pre[j]]\)
令\(h[j]=s[j]*2-s[pre[j]]\)
易知，当\(i\)增大时，合法的\(j\)越来越多，则想取的最大的\(j\)右移，可以考虑对\(\{h[j] |1 \le j < i \}\)进行排序，不断将合法点对 \((j,h[j])\) 加入集合\(S\)，对\(S\)关于\(j\)排序，取最大的\(j\)即可
两个优先队列可以实现，时间复杂度\(O(nlogn)\)
注意到对于\(x<y\)，如果\(h[y] \le h[x]\)，那么\(y\)会比\(x\)先进\(S\)，\(x\)永远没有机会取到，发现了单调队列的模型，可以用单调队列维护
p.s. 这道题我一开始就想到了贪心，但是后续的优化没想到(悲
p.s.s. 最后面的高精和生成数据懒得写了，依托答辩
p.s.s.s. ↑ 写出来了，但是空间优化很麻烦，用到了滚动数组，DFS还原答案等方法，建议看一下 link
P3648 [APIO2014] 序列分割
最最重要的性质：切的顺序与答案无关
然后就是斜优板子题
p.s. 应该数据范围有暗示，毕竟这题跟能量项链的结构几乎一致，却有\(O(n)\)的数据范围
细节
1、注意\(a[i]=0\)时会有\(x_i=x_{i-1}\)，此时斜率不存在
2、注意边界
P1450 [HAOI2008] 硬币购物
最近课内刚学排列组合，容斥用得多一眼就看出来了，之后不知道能不能看出来
P5339 [TJOI2019]唱、跳、rap和篮球
为数不多独立完成的一道紫题，纪念一下
题解各位神犇用了什么NTT、EGF之类的方法，然而我都不会（
此算法数学基础为：计数原理，容斥原理，插板法计数
球盒模型
有\(n\)个盒子，\(m\)个球，盒子有编号，球没有编号，允许盒子为空，求方案数
不妨先往每个盒子里放一个球，转化为不允许为空的球盒模型
插板法：即在\(n+m\)个球的\(n+m-1\)个空位插入\(n-1\)个隔板，相邻隔板为一个盒子，方案数为 \(C^{n-1}_{n+m-1}\)
解题思路
拿到题，直接容斥，设当前求队列中强制选\(i\)个鸡你太美，这\(i\)个鸡你太美的排列方案数即为往\(n-4*i\)个数里插\(i\)个相同的四元组，转化为球盒模型，即\(C^{n-4*i}_{n-3*i}\)
然后考虑强制选以外的元素，即为\(4\)中元素每种\(a[]-i\)个，排成\(n-4*i\)个元素的方案数
这个再搞一个DP即可，设\(g[j][k]\)前\(j\)种排了\(k\)个数的方案数
发现又是往元素里面插同种元素，球盒模型，最终方程为
\[g[j][k]=\sum^{min(a[j]-i,k)}_{l=0}C^{k-l}_{k}*g[j-1][k-l] \]时间复杂度为\(O(4*n^2)\)
然后合并强制选和不强制选的，容斥：
\[ans=\sum_{i=0}^{\lfloor \frac{n}{4}\rfloor}(-1)^i*C^{n-1}_{n+m-1}*g[4][n-4*i] \]由于每次\(a[]-i\)不一样，每次都要重做一遍\(g[][]\)，总时间复杂度为\(O(n^3)\)
后记
去好好学一学别人的解法
P1973 [NOI2011] NOI 嘉年华
（脑子抽了，连第一问都没想到
第一问
由于要把线段划成不交的两个部分，即被一个连续区间完全包含的线段只能放在一个会场，考虑划分转移
而“活动相对较少的嘉年华的活动数量的最大值”这个东西比较抽象，类比极差问题的“定边界法”，我们把一个区间选的活动数量压进方程
设\(f[i][j]\)为区间\([1,i]\)中的线段，划给第一部分为\(j\)个时，划给第一部分的最大数量
枚举划分点转移即可，时间复杂度\(O(n^3)\)
第二问
相当于先将线段\(i\)划给第一部分，在做第一问
继续利用划分思想，线段\(i\)一定被某个划分出的区间完全包含，枚举该区间\([l,r]\)，对\([1,l-1],[r+1,n]\)做第一问的划分DP即可，设\(g[i][j]\)处理后缀
由于要枚举\(l,r\)和前后缀第一部分数量\(i,j\)，总时间复杂度\(O(n^5)\)
考虑对“枚举第一部分数量\(i,j\)”优化，易发现\(f[L][0\sim n]\)是单调不增的，也就是说对于类似\(\displaystyle Ans_L(i)=\min(i,f[L][i])\)函数是个单峰函数，可以用二分求出最大值，于是考虑区间\([l,r]\)的答案：
\(\displaystyle\ \ \ \ \max_{i=0}^n\max_{j=0}^n\min(i+j+cnt[l][r],f[l-1][i]+g[r+1][j])\)
\(\displaystyle=\max_{i=0}^n\max_{j=0}^n\min(i+(j+cnt[l][r]-g[r+1][j]),f[l-1][i])+g[r+1][j]\)
令\(X=j+cnt[l][r]-g[r+1][j]\)，外层枚举\(j\)，则有
\(\displaystyle=\max_{j=0}^n(\max_{i=0}^n\min(i+X,f[l-1][i]))+g[r+1][j]\)
二分求解 \(\displaystyle\max_{i=0}^n\min(i+X,f[l-1][i])\)，可\(O(n\log n)\)求解该式
再把答案记到\(Ans[l][r]\)，对于线段\(i\)，枚举调用\(Ans[1\sim l][r\sim n]\)即可,总时间复杂度\(O(n^3\log n+n^3)\)
其实还有线性做法，不过用不到了
P6764 [APIO2020] 粉刷墙壁
求每个点是否可选，再做最小区间覆盖即可
暴力：\(O(nm)\)
优化：这里有一句话：\(\sum f(k)^2\le4\times 10^5\)，则\(\sum f(k)\le 800\)（我怎么没想到，还以为是\(O(\sum f(k)^2)\)的算法
容易想到，只存这\(800*n\)个值，直接dp即可
然而实现上我差点火候，直接map找前一个的位置，多了\(O(\log n)\)导致TLE，实际上只需要滚动数组把\(i,i+1\)的全部\(f[][0\sim k-1]\)存起来就行了
由于\(Subtask\)，搞了半天跟暴力没差（悲
标签：排列,max,复杂度,区间,蜘蛛,枚举,序列,动态,规划 From： https://www.cnblogs.com/zhone-lb/p/18518386