【题解】牛客挑战赛30 精

T1

这是一道模拟题。。。因为答案上界是 $(\frac{n}{4})^4$ ，所以，直接枚举+强力剪枝是可以过的。

当然，你也可以选择更有技术含量的方式：枚举a,b,c，再运用二维前缀和求出c+1到n有多少满足条件的d。时间复杂度的优秀算法。

T2

首先有一个显然的的做法，即枚举左端点，在移动右端点的过程中用set维护中位数。
但是这样太慢了，仔细分析一下，我们需要的是一个O(1)访问相邻点，O(1)插入的数据结构。
可以改成O(1)访问相邻点，O(1)删除，这样就可以用链表维护了,只需枚举左端点，从右往左减即可。复杂度

T3

为了简化问题，我们先考虑当这棵树是有根树时该如何计算答案。如果我们把删除的节点依次编号为1~n，显然每一种合法的删除方式对应一种合法的编号方式，而编号合法当且仅当对于除根节点外的每一个节点，它父亲的编号大于它的编号。为了计算，不妨这样想：对于一棵子树，我们通过父亲给它分配一组编号，表示子树的编号集合（初始集合为{1,2...n}）。然后，把最大的编号分配给子树的根节点。因为根节点的儿子间的编号是没有约束的，所以可以通过组合数来随意分配编号。设点x子树大小为 $sz_x$ ，答案就是：

$\Pi_{i=1}^n \frac{(sz_i-1)!}{\Pi_{j\ is\ a\ son\ of \ i}sz_j!}$

无根树的答案等于将每个点当成根的答案的和。换根DP维护上式即可。

T4

首先答案有一个显然的式子
$\sum_{i=l}^r\binom {i+n-1}{n-1} \binom {s-i+m} {m}$
这个式子抽象到平面上，可以看成(0,0)到(s,n+m),每次往右或者往上，其中经过线段(l,n)———(r,n)的方案数。
可以看成经过(l,n)下方而不经过(r,n)下方，注意n,m是可以支持枚举的，那么我们用经过(l,n)下方的方案数减去经过(r,n)下方的方案数即可。

T5

可以发现题目给的式子的实际含义就是仙人掌上的所有路径的总长度对Q取模的值。我们考虑每条边的贡献。可以发现：

1.对于树边(x,y)，这条边被包含的次数是，其中 $f_x$ 表示从x出发，不经过选定树边的路径数；

2.环上边的经过次数比较复杂。不过，同一个环上的每一条边被经过的次数都是相同的。

为了方便，我们可以先把仙人掌转化为圆方树，然后以1为根DP出 $g_x$ ：从x出发到子树中任一点结束的路径条数。注意每经过一个环，g的值就要乘二。因为有顺时针/逆时针两种走法。再换根DP一次就可以求出树边的答案了。

接下来重点分析一下非树边。对于一个长度为m的环，为了方便，设 $v_1$ 到 $v_m$ 为从环上的某个点出发，不经过环上边的路径数。这个东西可以在上一步中求出。那么，这个环中的每一条边被经过的次数都是：

$\Pi_{i=1}^m\Pi_{j=i+1}^mv_iv_j$

这个环的贡献就是环上的边权和乘上上式。

T6

如果我们能够构造一个多项式 $H(x)=\prod_{i有二次剩余} (x-i)^k$ ，那么再将该多项式与F(x)取Gcd可以得到答案多项式。

二次剩余有一个判断式 $x^{\frac {p-1} 2} -1 = 0 (\mod p)$ .
那么由代数基本定理, $x^{\frac {p-1} 2} -1 = \prod_{i有二次剩余} (x-i) (\mod p)$
现在问题是怎么将 $(x^{\frac {p-1} 2} -1)^k$ 与F(x)取Gcd。
注意到我们只需要先将 $(x^{\frac {p-1} 2} -1)^k$ 对F(x)取模，接下来两个多项式的次数就都是O(n)级别的。
$x^{\frac {p-1} 2 } \mod F(x)$ 和 $(x^{\frac {p-1} {2}}-1)^k \mod F(x)$ 可以利用快速幂算出。
复杂度 $O(n^2 \log 998244353)$
如果写多项式取模可以做到 $O(n^2+n\log n \log k)$