【题解】牛客练习赛64

A：怪盗-1412

将序列排列成 $11...1144.44411...11222..222$ ,这样可以得到最大化的子序列数量，答案为 $m*k*(n/2)*(n-n/2)$ ，时间复杂度 $O(T)$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780345

B：Dis2

与每个点距离为 $1$ 的点为这个点的度数。对于每个点 $u$ ，枚举和它有边相连的点 $v$ ，点 $v$ 对点 $u$ 的贡献为与点 $v$ 距离为 $1$ 的点的个数减去 $1$ （减掉 $u$ 这个点），时间复杂度 $O(n+m)$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780359

C：序列卷积之和

$\sum_{i=l}^r\sum_{j=l}^ra_i*a_j=(\sum_{i=l}^ra_i)*(\sum_{j=l}^ra_j)=(\sum_{i=l}^ra_i)^2$
$\sum_{i=l}^r\sum_{j=i}^ra_i*a_j=((\sum_{i=l}^ra_i)^2-\sum_{i=l}^ra_i*a_i)/2+\sum_{i=l}^ra_i*a_i$
设 $sum(x)=a_1+a_2+...+a_x$ 。
设+ $psum(x)=a_1*a_1+a_2*a_2+...+a_x*a_x$ 。
则 $\sum_{l=1}^n\sum_{r=l}^n\sum_{i=l}^r\sum_{j=i}^ra_i*a_j=$
$\sum_{l=1}^n\sum_{r=l}^n((sum(r)-sum(l-1))^2-psum(r)+psum(l-1))/2+psum(r)-psum(l-1)$
预处理前缀和统计前缀和出现的数量，即可得出答案，时间复杂度 $O(n)$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780364

D：宝石装箱

设 $g(x)$ 表示选出 $x$ 个箱子装不合法的宝石的方案数。
设 $f(x)=x*(x-1)*...*1=x!$ 。
那么 $g(x)*f(n-x)$ 为至少 $x$ 个箱子装了不合法的宝石的方案数。
根据容斥原理，答案为 $\sum_{i=0}^n(-1)^i*g(x)*f(n-x)$ 。
设 $a_i$ 表示不可以装入第 $i$ 个箱子的宝石的数量，注意到每个宝石只对应一个箱子。
初始时， $g(0)=1,g(k)=0(k>1)$ 。
然后相当于每次加入一个物品，当加入第 $i$ 个箱子，有 $g(k)=g(k)+g(k-1)*a_i$ ，那么通过背包就可以求出所有的 $g$ ，最后统计答案即可，时间复杂度 $O(n^2)$ ，常数很小。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780376

E：红色的樱花

如果 $sx=ex,sy=ey$ ，那么答案为 $0$ 。否则：
随机选择一个点 $x,y$ ，初始时，让 $k=0$ ，然后执行以下操作：
a.将点 $x+k,y+k$ 染色，再让 $k=k+1$
b.如果点 $x+k,y+k$ 已经被染色，则跳出，否则回到 $a$ 。
当 $k=lcm(n,m)$ 的时候，被染色的点构成了一个循环。
这样的循环的数量有 $n*m/lcm(n,m)=gcd(n,m)$ 个。
那么操作1转为花费 $a$ 牛币，跳到点 $x,y$ 所在的环的任意一个位置。
可以证明，操作1至多只需要执行一次。
如果执行0次操作1，我们只能进行横和列的移动，那么就是分别求 $sx+d*x1=ex$ $mod$ $n$
$sy+d*x2=ey$ $mod$ $m$ 的最小正整数解。
如果执行1次操作1：
1.牛牛和牛妹在同一个环，答案为 $a$ 。
2.牛牛和牛妹不在同一个环，那么通过列或者行的移动移动到牛妹所在的环，答案再加 $a$ 即可，观察环与环在行上移动和列上移动的影响，可以发现只在行上移动或者只在列上移动是最优的，分别求 $sx+(ey-sy)+d*x1=ex$ $mod$ $gcd(n,m)$ ， $sy+(ex-sx)+d*x2=ey$ $mod$ $gcd(n,m)$ 的最小正整数解即可，时间复杂度 $O(Tlogn)$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780369

F：如果我让你查回文你还爱我吗

先求出所有的回文半径，设 $p_i$ 为第 $i$ 个位置的回文半径，对于一个查询 $l,r$ ，我们要统计 $\sum_{i=l}^rmin(i-l+1,r-i+1)$ （这里暂时只考虑奇回文）。这样的时间复杂度为 $O(n^2)$ 。
让 $m=(l+r)/2$ ，那么我们就只需要对 $[l,m]$ 区间查询左回文，对 $[m+1,r]$ 区间查询右回文，消除了 $min$ 的限制。
同样，对于 $i$ 的回文半径，我们把它分成两条线段 $[i-p_i,i]$ 和 $[i,i+p_i]$ ，一条线段相当于对区间内的每个点权值加 $1$ ，对于一个查询 $[l,m]$ ，我们要求所有 $[i-p_i,i]$ 区间满足 $i<=m$ 的线段对区间 $[l,m]$ 的点的贡献和，对于 $[m+1,r]$ 的查询类似。那么可以将查询离线，用数据结构维护区间和。在线查询可以用可持久化数据结构维护。总的时间复杂度为 $O(nlogn)$ 。
标程：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43780554