A
注意到$sum (x_i-x_j) = n sum x_i^2-(sum x_i)^2$
$DP$求出选$i$个点横坐标总和$x$纵坐标总和$y$时距离平方最大值即可
B
先填$lfloorfrac{m}{n} floor n$个$n$, 然后递归考虑子问题$ ext{(m%n,n)}$即可
C
$2$操作可以用询问打标记实现, 问题相当于每次涂黑一个点, 询问一个点到所有黑点距离和
可以用点分树$O((n+q)log{n})$实现
D
n=1或n=24时合法, 否则不合法
E
F
G
设${dp}_{i,j}$表示$V^1$中第一行删除$i$个点, 第二行删除$j$个点的方案
假设删除第一行的点, 没有限制直接删即可
假设删除第二行的点, 如果$j<i-1$的话, 那么第二行挂的肉片可以直接删掉
如果$j=i-1$的话, 那么第二行挂的肉只有当$V^1_{i+1}$删除后才能删掉
那么在$V^1_{i+1}$删除前, 只能先删掉第二行挂的肉的左侧部分, 枚举这部分删除的长度即可
总复杂度$O(N^2)$
H
答案是$n+k-1+sumlimits_{i=2}^k (lfloorfrac{n}{i} floor+lfloorfrac{n-1}{i} floor)$, 可以整除分块
I
首先要知道拓展$Cayley$定理:
$n$个带标号点构成$k$个连通块的森林, 使得点$1,2,...,k$分别属于每个连通块的方案数是$k n^{n-k-1}$
考虑点$1$的贡献, 最后乘上$n$即可
假设$d(1)=x$, $1$所在连通块大小为$y$, 那么可以得到方案数为$inom{n-1}{y-1}inom{y-1}{x}x (y-1)^{y-x-2} f_{n-y}$
其中$f_n$为$n$个带标号点构成森林树, 枚举点$n$所在连通块大小, 可以得到$f_n=sumlimits_{i=1}^n inom{n-1}{i-1} i^{i-2} f_{n-i}$
那么点$1$的贡献就为$sumlimits_{x=1}^{n-1}x^2sumlimits_{y=x+1}^{n} inom{n-1}{y-1}inom{y-1}{x}x (y-1)^{y-x-2} f_{n-y}$
这样就得到单组数据$O(N^2)$的算法, 然后考虑优化
交换一下求和次序, 得到$sumlimits_{y=2}^n inom{n-1}{y-1}f_{n-y}sumlimits_{x=1}^{y-1} x^2inom{y-1}{x}x (y-1)^{y-x-2}$
$O(N^2)$预处理出$sumlimits_{x=1}^{y-1} x^2inom{y-1}{x}x (y-1)^{y-x-2}$即可
J
按题意模拟