bzoj2845,noi2012随机数生成器解题报告

 题意

给出\(m,a,c,x_0,n, g\)  \(  x_{n+1}=(a\times x_n+c)\%m\),求\(x_n % g\)

算法分析

该题可利用矩阵倍增来实现。利用矩阵乘法和矩阵乘法的结合律,有如下性质:

\[
\begin{bmatrix}
a_{n-1} & 1
\end{bmatrix}
\times
\begin{bmatrix}
a & 0\\
c & 1
\end{bmatrix}
=
\begin{bmatrix}
a_n & 1
\end{bmatrix}
\]

那么就有:

\[
\begin{bmatrix}
a_{0} & 1
\end{bmatrix}
\times
{\begin{bmatrix}
a & 0\\
c & 1
\end{bmatrix}}^n
=
\begin{bmatrix}
a_n & 1
\end{bmatrix}
\]

由于n较大,我们可以对矩阵进行快速幂,方法如下:

将n分解为2进制的形式,设置一个临时变量t,初值为x矩阵。

循环n的2进制位数这么多次,每次判断n的第i位是否为一,若为1,则ans=ans*t。最后t=t*t。

此外,该题会有两个long long相乘,会溢出。需进行快速乘法。方法同上,把t=t*t改为t=t*2,把ans=ans*t改为ans = ans + t即可。

代码中高亮部分即为快速幂和快速乘法。

代码

 

bzoj2844albus就是要第一个出场解题报告

题意

给出n个数,在这n个数中选任意多的数进行异或,共产生了2n个含重复数字的数,现给出一个数q,问若将q插入这2n个数中,q是第几小的

算法分析

先对着n个数进行高斯消元,得到m个非零数和n-m个0,那m个非零的值就可组成2n种数,每个重复2n-m次。只要按位统计q在其中排在第几位就可以了。

代码