题解-AtCoder Beginner Contest 238
A - Exponential or Quadratic [1]
给定 \(n\)，判断 \(2^n>n^2\) 是否成立。
只有 \(n=2,3,4\) 时不成立。
B - Pizza [1]
有一个圆，每次描一条垂直的半径，再旋转 \(A_i\) 度。问最后距离（度数）相差最远的两条描痕差多远？
直接模拟这个过程，每次记录描痕距离起点多少度即可。
C - digitnum [3]
\(f(n)\) 代表所有与 \(n\) 有相同位数的数的个数，求 \(\sum\limits_{i=1}^{n} f(i)\)
\(1\le n\le 10^{18}.\)
按不同位数来考虑，比如十位数的 \(f\) 即为 \(n-9\)。前者求和即为自然序列求和，后者是一个常数。于是可以 \(O(\log_{10}n)\) 做。
D - AND and SUM [3]
给定 \(a,s\)，判断是否存在 \(x,y\) 满足 \(x+y=s,x\& y=a\)。
首先有结论 \(x\& y+x\| y=x+y\)，于是可以求出 \(x\| y\)。那么只需判断这个值是否大于 \(0\)，是否包含 \(a\) 即可。
E - Range Sums [4]
给定 \(N\) 和 \(Q\)，以及 \(Q\) 对 \((l,r)\)。判断在知道 \(\sum\limits_{i=l}^{r}a_i\) 的情况下能否知道 \(\sum\limits_{i=1}^{n}a_i\)。
做过一万遍了。考虑转成前缀和然后差分约束。我们把 \(a,b\) 连边代表知道 \(a,b\) 中的任意一个都可以知道另一个的值。所以最后判断 \(n\) 和 \(0\) 是否在一个连通块即可。
F - Two Exams [4]
给定 \(n,m\) 和两个排列 \(p,q\)，求有多少种选 \(m\) 个元素的选法使得不存在 \(x,y\) 满足 \(p_x>p_y\) 且 \(q_x>q_y\)。其中 \(x\) 被选了 \(y\) 没被选。
\(1\le n\le 300\).
看到这个数据范围猜也能菜到 dp 了。考虑状态，首先肯定要做一个背包，关键是这个偏序关系。那么不妨先给第一维排一个序，然后再记一维 \(k\) 表示没选的元素最小的 \(q\) 值为 \(k\)。那么只有 \(q_i
G - Cubic? [4]
给定 \(N\) 和长为 \(N\) 的序列 \(A\)，\(Q\) 组询问 \(l,r\)，判断 \(\prod\limits_{i=l}^{r}A_i\) 是否是完全立方数。
\(1\le N, Q\le 2\times 10^5,1\le A_i\le 10^6\).
有什么哈希一类的不确定算法，但这里讲一种复杂度稍劣的确定性算法。
先根号分治，小于 \(1000\) 的质数直接暴力判断。然后大于 \(1000\) 的质数每个数最多有一个，于是莫队时候插入删除就都是 \(O(1)\) 了。
至于不确定算法，可以随机权值，然后做三进制不进位加法。
Ex - Removing People [7]
\(n\) 个人排成一个圆，给定每个人的朝向。一共 \(n-1\) 次操作，每次选择一个人，然后将其看到的第一个人删掉并有代价即为两者距离。
这里距离的定义为以朝向为正方向，之间隔了几个人。并不是最短距离。求代价的期望值。
\(1\le n\le 300.\)
感觉最难的还是转换问题。考虑一个删除排列 \(P\)，\(P_n\) 是最后剩下的那个。那么可以从后往前，也就是 \(P_n,P_{n-1}...\) 这样逐个确定每个值是在哪。而这时相当于确定之后有两个情况，在 \(P_{i+1},P_{i+2},...,P_{n}\) 里这些已有的选最靠近自己的那两个，看是否满足条件。
暴力的思维是 \(O(n!)\) 枚举，通常这样的暴力都可以用dp优化，因为有很多冗余的状态。显然对于已经确定的两个位置，之间的那些位置和这两个位置之外的部分就无关了。那么考虑区间dp。不过这是个环先得断环成链。之后记 \(f[i,j]\) 代表往开区间 \((i,j)\) 填的方案数。\(i,j\) 是已经填好了。转移考虑枚举一个 \(k\) 作为区间内第一个被选的位置。\(c_1\) 代表 \(k\) 有几种选择（选择 \(i\) 还是 \(j\)）。有方程 \(f[i,j]=\sum\limits_{k=i+1}^{j-1}\binom{j-i-2}{k-i-1}f[i,k]f[k,j]c_1\)。这里组合数代表目前状态共有的 \(j-i-1\) 种选择去掉 \(k\) 再选 \(k-i-1\) 放到前面去。
然后记 \(g[i,j]\) 代表代价，最后答案即为 \(\dfrac{\sum\limits_{i=1}^{n}g[i,n+i]}{n!}\)。转移类似，不过这里需要计算 \(k\) 的贡献（不计算 \(i,j\) 互相的贡献）。需要记录一个 \(c_2\)。具体细节可以参考代码 45-48 这几行。感觉比写在这里清楚。
code