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即可。

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

代码

 

生活总有如此多的惊喜

今天已经是托福培训课的第3天了。下课时,听到有人喊我的名字,抬头一看,竟是我童年时的小伙伴高*。我和他也有几年没有见了,各自都成熟了不少。但我和他,却选择了截然不同的道路。一路上,和他聊着天,回忆着过去,畅想着未来,仿佛又回到了几年前。

说到这里,又想起一件好玩的事。昨天,妈妈和我说,我楼上的邻居和svsfzhc在一个班学托福。我心想这是多么偶然啊。昨天上午,我却偶然在天津中心的电梯里遇上了我的邻居。是不是哪天我也遇得上svsfzhc  :)?

PS:在这里介绍一下svsfzhc:某神犇,点击这里进行膜拜

浅谈《飘》

    近日,闲来无事,将《飘》通读一遍,颇有些感慨。

    该书的时代背景和人物是现实的写照。该书描绘了一个典型的随着南北战争失败而逐渐落魄的老南方社会。而原社会的统治阶级绝大部分都没有随着形式而改变,从而灭亡。而这和《红楼梦》中的四大家族是多么的相似,和《大(貌似是关键字)江()大%……海@1949》的战争场面又是多么的吻合。皆为战乱使得原先的统治阶级变得落魄。而这些书的主人公们不同的态度决定了他们不同的命运。

       在这些书中,原来的被统治阶级(分别为黑奴,丫鬟,农民),与原先的统治阶级和好相处(《飘》中描绘了白人要负责给黑人教育、医疗等一系列责任,同时也限制将黑人卖给没有能力的白人,《红》中的情景又是多么的类似)。而新的革命者却鼓吹、利用这些原先的被统治阶级,来达到他们自己的目的(黑人奴隶解放,土地革命。。。),使其与原先的统治阶级闹翻,最终以达到自己的目的。可当这一切都完成之后,这些帮助原先的革命者的底层人民却又将再一次落入底层。(解放后的合作社,北方人并不认可黑人)。最终,他们只得沦为悲惨的被人利用者。现在不也是如此吗?底层人民永远是最悲惨的。

      再来看原先的统治阶级。在《飘》中,失势的统治阶级又被分为两类:努力顺应新的弱肉强食的社会的人(以郝思嘉和白瑞德为代表),这也就意味着他们抛弃了过去,而只是奋力在新环境下存活。这也导致了他们为了利益而舍弃旧有传统,与原先的阶级分离。成为遭人愤怒的叛徒,而在心中留下无穷的道德的负担。而另一类则是以希礼.威尔克斯为代表的对旧生活的坚守,因为现实已经改变,他们只得向后看着过去,而沉浸在现实的痛苦之中。最终由于守着过去而不前进最终安详的死去。

       以上这些在现实的中国社会都有写照,荣毅仁不就是前者的写照吗?而在我看来,无论社会如何变化,都要永持一颗不断奋进的金子般的心。《飘》的作者并未对其的立场在书中阐明,只是最后坐拥大量财产的郝思嘉最后背负了无穷无尽的骂名,孤苦伶仃。而大部分老南方的拥护者则生活在过去的世界里,依靠施舍活命。二者结局皆十分悲惨。第二种在我看来绝不可取,而第一种在郝思嘉嫁给白瑞德之前,她是正确的,因为在她的心底认为唯有钱能保护她,而唯有钱才能保证她不受北方人的侮辱,因为她赚钱的目的是支持南方,这是可取的。而她在第三次结婚后却抛弃了这一切,使其丧失了金子般的心。而在现在,不也是一样吗?那么多的制假售假行为就是因为心底最根本的基础丢失了。某人曾说着过,饱受内战的民族的人民,必将互相猜忌、自保、互相倾轧。现在看来,这又是正确的。历史总是在不断的重演。

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

题意

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

算法分析

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

代码

 

poj2104主席树

题意

给定一个数列,给出若干个询问(l,r,k),求出[l,r]区间内第k小的数。

做法

用若干棵线段树分别维护前缀Si的离散化后的该数的个数,即在某棵线段树中,第i个位置表示离散化后大小为i的元素的个数,查询时在线段树上进行二分。

代码