Day 5

T1

先求离散对数，可以做到 $\mathcal O(\sqrt(n\times MOD))$。

然后就变成了区间加，查区间 $\gcd$。答案是 $\frac{p-1}{\gcd(a_l,\dots,a_r,p-1)}$。

我擦怎么过不去！！！

考虑你只关心他怎么干掉一个 $p-1$ 因子。所以只需要求出他们的阶的 LCM。阶可以暴力求。

T2

考虑所有 $\leq m$ 的点，他们形成了若干个连通块。容斥预处理大小为 $i$ 的连通图数量 $f_i$。

然后对于 $>m$ 的点，他最多只能连接一个联通块。这样就可以随便预处理出 $g_{i,j}$ 表示 $i$ 个 $\leq m$ 的点，$j$ 个 $>m$ 的点构成的一个合法连通块数量。

然后对 $\hat G$ 做一个 $exp$ 即可。学习了一下二元生成函数 exp，所以暴力可以做到 $\mathcal O(n^3)$，可以 FFT 就能做到 $\mathcal O(n^2\log n)$。

T3

$n$ 个 $k$ 位二进制数异或和为 $0$ 的方案数是 $2^{k(n-1)}$。

考虑如果只有一行怎么做。$f_i$ 表示 $i$ 个互不相同的数异或和是 $0$ 的方案数。转移是 $f_i=(2^{k})^{\underline{i-1}}-f_{i-2}(i-1)(2^i-(i-2))$。

加入了第二行，假设第一行比第二行长，考虑枚举有 $i$ 列上下相等，先确定这 $i$ 列的取值：$(2^k)^{\underline i}$。然后方案数是 $(2^k-i)^{\underline{n+m-2k-1}}$……吗。不是。因为你的最后一个数可能会和这 $k$ 列钦定的相等。

既然容斥不大好做，那就直接正着计数。钦定第一行互不相同，然后对于第二行考虑他们是否和第一行的某个数相等。考虑计算 $g_{n,m}$ 表示 $n$ 个数的排列，其中前 $m$ 个数不能和自己相等，其余任意的方案数。

考虑从 $g_{n,m}$ 推到 $g_{n,m-1}$，若 $p_m=m$ 则可以把它删掉后方案数是 $g_{n-1,m-1}$。所以 $g_{n,m-1}=g_{n,m}+g_{n-1,m-1}$。

对于 $g_{n-1}$ 怎么递推。从 $g_{n,m}$ 里考虑 $p_m=x$，若 $p_x=m$，删掉 $p_m$ 之后，分 $x<m$ 和 $x>m$ 讨论，则方案数是 $g_{n,m}=(m-1)g_{n-1,m-2}+(n-m)g_{n-1,m-1}$。所以考虑维护二环组 $(g_{n,m},g_{n-1,m-1})$。这样可以 $\mathcal O(1)$ 推出 $g_{n-1,m-2}$ 和 $g_{n,m-1}$。复杂度 $\mathcal O(n)$。

Day 6

什么傻逼场

T1

先判掉 A 能一步秒 B 的情况。

首先一个人的斩杀线是 $mx+rg$。容易发现斩杀线大的人一定不会输。

然后判一下斩杀线大的人能不能把他杀掉。如果他 $mv$ 大于另一个人的那就可以把两者的距离削减到 $mv2+rg2+1$，只需要判 $mv1+rg1\geq mv2+rg2+1+mv2$ 即可。否则两者距离可以削减到 $\max(mv2+rg2+1,d-mv1)$，判 $mv1+rg1\geq d+mv2$ 即可。