CQOI2018简要题解

破解D-H协议

$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$

直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ,然后答案就是 $g^{ab}\bmod P$ 。

代码

社交网络

【模板】有向图矩阵树定理。

代码

交错序列

首先推式子: $x^ay^b=(n-y)^ay^b=\sum\limits_{i=0}^aC_a^in^i(-y)^{a-i}y^b$ 。

发现只要求和 $y$ 有关的项。

设 $f[i][j][0/1]$ 表示前 $i$ 个数,最后一位为 $0/1$ ,所有满足条件的序列中 $1$ 的个数的 $j$ 次方和。

转移有三种:

  • $f[i-1][j][0]\to f[i][j][0]$
  • $f[i-1][j][1]\to f[i][j][0]$
  • $\sum\limits_{k=0}^jC_j^kf[i-1][k][0]\to f[i][j][1]$

然后用矩阵快速幂优化一下转移,最后再代回去算答案即可。

代码

解锁屏幕

设 $f[S][i]$ 表示已经使用了的点集为 $S$ ,现在在点 $i$ 的方案数。

转移直接枚举下一步往哪走即可。

注意到要走的时候路径上的点必须全部用过,那么可以预处理出 $i-j$ 跨过了哪些点。这个随便搞搞就行了。

代码

九连环

打表可以发现答案为 $\left\lfloor\frac{2^{n+1}}{3}\right\rfloor$ 。

写个 FFT 优化高精度乘法即可。py 大法好

代码

异或序列

记 $s[i]=a[1]\oplus a[2]\oplus ... \oplus a[i]$ 。

问题变为 $[l-1,r]$ 中,有多少对 $(x,y)$ 满足 $s[x]\oplus s[y]=k$ 。直接莫队即可。

代码

最后修改:2019 年 09 月 27 日 01 : 14 PM

发表评论