懒，随缘更。
Round 1
优惠购物
看完题会有几个结论：
- 如果一次性使用了 \(c\) 个金币，那么在更前面使用更优。
- 对于每个数最上面的 \(A_x\bmod c\) 个金币，优惠券越前面用越好。
我们来考虑一下优惠券的使用，优惠券越前面用越好吗？不一定，这样优惠券在后面产生，可能用不到。优惠券越后面用越好吗？也不一定，有可能优惠券实在太多了，需要都用优惠券。
这里产生了一个矛盾，但是是有办法解决的。我们从前往后考虑每个物品，并优先使用优惠券。接着我们可以反悔。假设我们对 \(i\) 使用了 \(C_i\) 个优惠券，那么最上面 \(A_i\bmod c\) 个优惠券是不会被用金币反悔的，因为这里是一个金币换一个优惠券，肯定不优。中间有若干段整段的 \(c\) 个优惠券，如果用 \(c\) 个金币反悔，会得到 \(c+1\) 个优惠券。最后有一个非整段的优惠券，同样的，如果用金币去完全兑换，可以多得到一张优惠券，否则只能得到金币对应数量的优惠券。
从这里可以看出，对于一个物品，如果有可以反悔的一段优惠券，肯定优先使用金币去反悔这段优惠券，而不是直接用金币去购买这段商品。这样大体上已经完成了，最后需要考虑需要的优惠券不足以兑换一整段之前的优惠券的情况，这时需要考虑到底是将前面的一段优惠券兑换一部分，还是将金币留给自己，这个可以根据留给自己会/不会多一张优惠券，以及两者的大小关系来判断。
用堆维护，每次取最小的，时间复杂度 \(O(n\log n)\)。
网格图最大流计数
好像有点超前了/qd，这里就写一写部分分。
\(s_{i,j}=0\) 的点可以看作这个点不能通过，流可以看作不相交路径，也就是说，我们需要求一张有障碍的网格图上，不相交路径的最大值以及计数。
对于 \(n=m\) 且最大流为 \(n\) 的情况下，可以直接上 LGV 引理，先 \(O(nk^2)\) dp 求出每对起终点之间的路径条数，然后直接求矩阵行列式的值即可。
对于 \(n\leq 10\) 的，有两种做法，一种是枚举起终点集合，然后求行列式。另一种是考虑每个起点，状压有哪些终点选取过了，然后选取一个终点，计算排列逆序数的贡献，复杂度 \(O(2^kkn)\)。
然后要用什么 Pfaffian ，不会了。/hsh
Round 2
序列
1s 跑不过去 7e8 次乘法取模什么成分？long long 改 int 快一倍什么成分？
枚举值域 \(m\leq n\)，大的显然可以插值。倒着dp，如果形成了 \(a_x>a_y,x<y\) 的情况，那么将 \((a_x,a_y)\) 之间的数视作删掉。则可以设出 dp 状态：\(dp_{i,j,k}\) 表示从后往前到了第 \(i\) 个，还剩 \(j\) 个数，目前最小值为 \(h\) 的方案数。转移要么更新最小值，要么和最小值组成 \(20\) 形状，就删掉了中间的数。直接 dp 是 \(O(n^5)\) 的，进行一些简单的优化就可以变成 \(O(n^4)\)，加上插值总共可以做到 \(O(n^4+nq)\)。
没有创意的题目名称
看到这个题一脸懵逼，于是先看个特殊性质，发现 \(lim_i=i\) 的答案是 \(\frac{n(n+1)}{2}+1\)，那个 \(+1\) 是 \(f_i=i\) 的。其余答案的序列应该长成：存在一个 \(k\) ，满足 \(i\leq k\) 的有 \(f_i=i\)，\(f_{k+1}\) 在前面 \(i\) 个随便选一个指向过去，之后 \(f_{k+2}\) 以后的可以唯一确定且一定有解，构成了一个循环。
然后写个暴力会发现不仅是这种情况，几乎所有情况下都有循环节。
先证明一下存在循环节。如果存在 \(f_i=f_j\)，则 \(f_{i+1}=f_{f_i+f_1}=f_{f_j+f_1}=f_{j+1}\)，也就是说一旦出现两个相同的数，就会形成循环节。
这里分 \(f_i=0\) 和 \(f_i\not=0\) 讨论。先看 \(lim_i=0\)，枚举前面 \(f_i=i\) 的到哪里，假设到 \(i\)，那么 \(f_{i+1}\) 会不指向自己。如果 \(f_{i+1}\) 指向 \([0,i]\)，那么可以像上面直接判断，否则 \(f_{i+1}\) 指向更后面的数。因为 \(lim_0=0\)，所以 \(f_{f_i}=f_i\)，也即如果 \(f_{i+1}\) 确定后一定会形成循环节。
但是当 \(i+1\) 指向后面时，形成合法序列还要满足一些其它条件。首先是，\(2(i+1)\leq n\)，因为若 \(2(i+1)>n\)，那么 \(f_{i+1}\) 与 \(f_{n-(i+1)}\) 加起来就会大于 \(n\)，不合法。然后可以推出 \(2f_{i+1}\leq n\)。可以发现，这对于循环节内所有指向后面的数都是成立的。其次，如果循环节内某个位置 \(f_i\) 指向了 \(i-c\)，则根据定义，\(f_{i+1}=f_{i-c+1}\)。也就是说，如果某个位置指向前面了，那么接下来的位置都要指向前面。
可以证明，有上面两个性质，就是充分的，于是就可以 \(O(n^3)\) 计数了，进行一些剪枝就可以通过。或者可以维护区间乘积做到 \(O(n^2)\)。
然后考虑 \(f_0\not=0\)。首先，有 \(f_0=f_{f_0}=f_{2f_0}=\dots\)，又构成了循环节，也就是说，循环节是从 \(0\) 开始的，所以只需要枚举循环节长度 \(c\)，然后对于循环节每个位置的取值，要么是指向和自己相同的数，要么均指向加上一半循环节长度的数。直接和上面类似计算就是 \(O(n^2)\) 的。