pts:25 + 20 + 0 + 30 = 75
最惨淡的一场。
出现的最大问题是脑子掉线。。。。
今后考试策略：
拿到题先读完所有的题，然后把所有能写的暴力全敲完之后再来想正解。
考试一定要带脑子 ！！！
题目描述
给出三个整数 \({x,y,P(1\le x,y<P)}\), \({P}\) 为素数，可以重复对 \({x}\) 执行如下操作：选择一个整数 \({z\in[1,P-1]}\) ，花费 \({|x-z|}\) 的牛币，使得 \(x=x\times z\bmod P\)。
最小需要花费多少牛币才能使得 \({x=y}\) ?
设 \({ans(i,j)}\) 为当 \({x=i,y=j}\) 时的答案，为了减少输出，你需要输出
\({\sum\limits_{i=1}^{P-1}\sum\limits_{j=1}^{P-1}ans(i,j)*t^{(i-1)*(P-1)+j-1}\bmod 998244353}\)
数据范围
\(2 \leq P \leq 2000\)
考试的时候真没忘建图那方面想，然后就草草打了个暴力走人了。
solution
对于每一个操作，相当于从 \(x\) 向 \(x * z \mod P\) 建一条边权为 \(|x - z|\) 的边，然后到 \(y\) 跑一个最短路就好了。
30pts
当 \(P \leq 500\) 直接 \(Floyed\) 就好了。
但由于数据水或者牛客神机太快了，这玩意赛时能过 \(85\) ，现在加强了数据，但是还能过 \(75\) 分，就挺反人类行为的 = =
code
题目描述
有 \(n + 2\) 个整数 \(a_0, a_1, \dots, a_n, a_{n + 1}\)
你需要做确切地 \(n\) 次操作，每次操作以下形式：
选择一个整数 \(x\) 满足 \(a_x \neq 0\), 使得 \(a_x\)， 令 \(l = \max_{i < x, a_i = 0}(i), r = \min_{i > x, a_i = 0}(i)\)
此次操作的操作为 \(\max\{a_l, a_{l + 1}, \dots, a_{x - 1}\} + \max\{a_{x + 1},\dots, a_{r - 1}, a_r\}\) 牛币
有多少不同的操作方式使得操作花费的牛币最少，两种操作不同当且仅当两种操作的操作序列不同。答案对 \({998244353}\) 取模。
数据范围
\(1 \leq T \leq 10\)， 每个测试点 \(|n|\) 的和 \(\leq 10000000\)
solution
这道题我的 n! 过掉了 \(n = 20\) 的数据就挺反人类的 = =
这道题 \(n^3\) 能过也挺反人类的 = =。
正解是个卡常。。。。
10pts
枚举全排列就好了。
20pts
状态压缩，计算代价，对比代价，得出答案。
70pts(实测 90)
设第一个操作的人的编号为 \(x\)， 在 \(x\) 进行操作 \([1,x−1]\) 和 \({[x+1,n]}\) 的操作就独立了，这两段区间进行操作不会对另一段区间的价值产生影响，因此可以进行区间 \({dp}\)。
设 \(f_{l, r}\) 表示对 \(l, r\) 区间进行操作的最小代价。
显然 \(f_{l, r} = \min\{f_{l, k - 1} + f_{k + 1, r}\}\)
设 \(g_{l, r}\) 为 \([l, r]\) 区间内最小操作的序列数量，枚举断点 \(k\)。
显然只有当 \(f_{l, r} = f_{l, k - 1} + f_{k +1, r}\) 才可以转移。
\(g_{l, r} = g_{l, r} + g_{l, k - 1} \times g_{k +1, r} \times C_{r - l}^{k - l}\)
因为两个序列之间的操作顺序先后都可，所以就有 \(C_{r - l}^{k - l}\) 种方案。
复杂度： \(n^3\)
code
100pts
实际上每次先操作区间最大值是最优的，因此没有必要对区间的所有数都进行枚举，而只枚举区间最大值，时间复杂度 \(O(n^3)\)
code
100pts
对于一段区间 \([l,r]\)，如果存在 \({a_i=a_{i+1}=\max\limits_{i=l}^r(a_i)(i\in[l,r))}\)
此时 \(i, i + 1\) 谁先选择没有关系，因此有 \(g_{l, r} = g_{l, i - 1} \times g_{i + 1, r} \times C_{r - l + 1}^{i - l + 1}\)
因此当碰到两个最大值连续出现时，直接将整个区间划分为两段，最大值不连续则仍然枚举所有最大值。时间复杂度 \(O(n^3)\)
定义无穷序列 \({f：f_1=1,f_{n}=f_{n-1}*2+1}\)
定义函数 \({G(x)=\min\limits_{f_i\ge x}(f_i})\) \({dp_{c,0}=0,dp_{c,i}=max(dp_{c,i-1},[((i*c)\&G(i))==i]*i)}\)
其中 \({[p]}\) 为真值函数，当 \({p}\) 为真返回 \({1}\)，否则返回 \({0}\)。
求 \({\sum\limits_{i=0}^ndp_{c,i}}\bmod 998244353\)
数据范围
\(1 \leq T \leq 10\) 每个测试点 \(|n|\) 的和 \(\leq 10000000\)
solution
20pts
直接模拟题意就好。
100pts
设 \(G(i) = 2^{t + 1} - 1\) (\(G(x)\)必然是这样的形式，其中 \(t\) 为 \(i\) 二进制的最高位)，则 \(x \& G(i)\) 相当于 \(x\mod 2^{t + 1}\)，则：\((i\times c) \& G(i) = i \rightarrow (i \times c) \mod 2^{t + 1} = i \rightarrow i \times (c - 1) \mod 2^{t + 1} = 0\)
设 \(c - 1 = 2^p \times x\)，则 \(i\) 需要含有因子 \(2^{t + 1 - p}\)。
设 \(m = |n|\)，我们可以枚举 \(t\)， 如果 \(t < m - 1\) 则 \([2^t, 2^{t + 1} - 1]\) 内的所有数最高位都为 \(t\)，设 \(g = t + 1 - p\)， \(i\) 含有因子 \(2^g\) 即 \(i\) 的低于 \(g\) 位的全为 \(0\)，这样的数为 \(2^t, 2^t + 2^g, \dots, 2^t + x\times 2^g(2^t + (x + 1)\times 2^g = 2^{t + 1})\), 这是个 \(x + 1\) 项的等差数列，很容易求和，同时每个数对答案贡献了 \(2^g\) 次。
当 \(t = m - 1\) 时，由于 \(2^{t + 1} > n\), 我们需要满足，\(2^t + x\times 2^g \leq n \rightarrow x = \lfloor \frac{n}{2^g}\rfloor - 2^{t - g}\)，对这个 \(x + 1\) 项的等差数列计算贡献后，由于最后一项被计数了 \(2^g\) 次（计数范围为\([2^t + x\times 2^g, 2^t + (x + 1)\times 2^g - 1]\)），此时多计数了 \(2^t + (x + 1) \times 2^g - 1 - n\) 次，把这个贡献减掉就好了。
code
100pts
题目描述
给出 \({n}\) 行 \({m}\) 列的矩阵，第 \({i}\) 行第 \({j}\) 列的元素为 \({a_{i,j}}\) ，找出满足以下条件的三元组{(i,j,x)}(i,j,x)的数量：
数据范围
\(1 \leq k \leq n\times m, 1 \leq a[i]\leq 100\)
solution
用 \(bitset\) 记录颜色种类。
在边长扩展的过程中，不同数量的数只会增加不会减少，具有单调性。于是可以二分找到不同数量 \({<k}\) 的最大边长 \({x}\) 和不同数量 \({\le k}\) 的最大边长 \({y}\)，\({y-x}\) 即为固定一个左上角符合条件的正方形的数量。
这样需要处理 \({O(n^2logn)}\) 个查询，每个查询查询一个正方形内不同颜色的数量，由于是正方形，故可以采用二维 \({st}\) 表来做。