(5)       Secret Code

求给定 A、D、 P、 M， 求A^x == D (mod P) ，这样的x，满足0<=x<=M的个数。

P<2^31  M<2^63

这个题目比较麻烦。

先要求出a^x==b (mod c)的最小的x

大概做法：

       提取若干个a出来，首先如果a和c不互质，并且最大公约数g能被b整除的话，

则把它提取出来。同于式两边同时除以g,，由同于的性质,c也除以g。这样反复提取了若干个a，注意这时c变为c’，直到c’与a互质或者它们的最大公约数不能被b整除。

假设前面提取了i个a出来，最后式子变成了

t*a^y==b’ (mod c’)

这里的t实际上是由1每次乘上（a/g）的结果（注意g也在变化）。经过这样的变化之后，事实上y=(x-i)，另外如果在i此之内已经找到了解就算找到了。这样的过程至多持续log(max(b,c)) 次，因为b和c每次至少除以2.。这样做的好处是有(t,c)=1 这对后面直观重要。

很久没写了，有工夫会补之前的。。。

(1)       Chain Factor

模拟题，直接模拟就行。细节就是，消去一些球后，其他球会下降。不过，直接实现起运行速度并不快。

(2)       Copy Triangle

就是求一个区域的整点个数。空白都是三角形，所以区域很规则。问题是如何表示这个区域。可以把一个模式看作上半个正方形框和下边完全空白的半个正方形的组合，即整个模式看作正方形。然后空白的区域只要记录它的右下角或者左上角就可以了。大概做法是，给定(x,y)，递归判断这个点所在的区域，（分为在边界上、在下半空白区域内、以及其他三个区域内），累计空白的点数（用乘法），得到区域的一个标识（左上和右下角坐标）。然后，对每个给定的点都如此做，对统计的空白点数求和，同样的区域标识只累加一次（用map）。还要注意使用long long。

(3)      It's never too late

给定n个木板(n<=16)，可以连接，求能组成的最大矩形面积。不大会这种搜索题，但是很感兴趣。我的做法比较诡异，我先考虑前一半的木板，用bit位表示状态，如果m=

   貌似有两个星期没写了。好像啥都没干啊。值得写的上周，师父去美国了，上周五研究了半天三国杀……不过好像很复杂的样子。

   上周六去龙泽找同学——一个微软的牛人、一个百度牛人，见面都给了我名片-.- ……

   上个月底的《夜店》中的爱情、 这个月初《后天》中的亲情、友情、这个月中《贫民窟中的百万富翁》中的巧合、黑色幽默、淡淡的辛酸都给我留下了深刻的印象。

   这个月，搞了2次“我把经验留下来”活动——请优秀的同学、师兄、师姐来座谈交流。

   今天似乎要帮人搬家——从双榆树东里到知春路。

   要放假了～～～～

   最近，做了不少事……其实，也没多少。

   周日（昨天），去中国美术馆了，免费参观。对于美术，乃至艺术，我向来是不敢亵渎的，看热闹去。不过，去看了还是受益匪浅，看到了一些名画……陶冶了情操。

   对于画的欣赏，好像挺外行的。小时候很喜欢看工笔画，认为一笔一画的写实，很不错。后来，感觉变了。喜欢写意，认为心中有感受，而不应拘泥于表现手段，但是似乎还没到能欣赏抽象画的层次…… 雕塑和画差不多，貌似也只能看热闹。版画嘛，我个人是不喜欢的，认为它太死板，过于强调线条，而又不具备工笔画的细致入微。油画也看了不少，一般有一定距离才能看出美感，而有些油画好像有距离也不能看出什么，并且用西洋的油画手段表达我国特有的主题色彩，也是一种创新。看了很多，很多人在看，在临摹，在谈论，在学习，在思考。

   美术馆禁止拍照，偌大的几层楼的展馆，有很多服务员，她们主要任务不是维持场内秩序。然而，我听到的最多的一句话是“您好，这里不允许拍照。”。被警告的人似乎那么心安理得，很潇洒地就这么——一笑置之，似乎没有一丝羞赧。一切都是那么理所应当。

    记得三余月前，我参加了团委的一个纪念活动，活动的主要目的是纪念五四运动就是周年以及科学院建院就是周年，在活动中我参观了鲁迅纪念馆和郭沫若故居。（他们：新文化运动的发起者之一和科学院首任院长）

    活动结束后，参与人员都写了心得体会，提交上去之后，貌似反馈说我写得还可以。今天，我惊喜地发现我的那个心得体会刊登在计算所所刊上了。

    一切，源于无心……

    很久没写博文了，因为我觉得无可写。深圳之行，似乎只是一片空白。

    乘火车，火车20+小时凌晨4点就到深圳火车站那了，看书，在车上看完了一本中等厚度的红楼趣谈的书。（赞速度，我可是从头看的）我们打车到了酒店，由于没到中午12点，暂时不能入住——ft。于是，我和朋友随便乘了趟公交到了蛇口，那是一个港口，知道了从那里可以乘船去香港、澳门等。于是回来，到深圳大学逛了逛，“世界之窗”门口看了看，深圳的地铁坐了坐。其实在正午前酒店已经可以入住了，但我们12点后才回去。中午，联系了在深圳的同学，毕竟3年没见面，吃饭，下午没事做，去K歌了，这是在深圳的第一天——很累，但是最快乐的一天。

    后面的几天——打酱油，零记忆。某天晚上，去了我那个同学“家”——在深圳租的房子。印象最深且最多的娱乐活动——打扑克……后来，我们换了个酒店，临海，很近有个免费开放的海滨浴场，可惜没机会游泳…… 遗憾有三：（1）鲥鱼刺多 （2） 红楼未完 （3）临海未游…… （参见 张爱玲 《红楼梦魇》）

    终于盼到周末，活动也结束了。我的火车票是迟一天的，于

    高温假2个星期，就要在深圳那边度过一个多星期。

    -_- 随身只带3本书——祝自己一路顺风。

    今天，又下雨了，而且还不小。伞在实验室，不在宿舍……郁闷了。想到《童年》那首歌，“总是要等到睡觉前，才知道功课只做了一点点。总是要等到考试以后，才知道该念的书还没有念……”。对我来说，总是在每个艳阳天，身边总放着三把伞。总是要等到下雨时，才知道伞都不在身边！按原来的调子唱出来，还蛮是那么回事的…… 百忙之中，发现宿舍有个一次性的塑料雨衣。

    下周要去深圳了，火车，要将近30小时，还是不晚点的情况，这貌似还是很恐怖的。

    十多天没写博了，今天忽然想起来也就写写……

    这次月赛的题目，质量很高。原因是这些题目都是浙大校赛和浙江省省赛的备选题目。因为校赛和省赛比完了，这些题没有用到（因为校赛省赛要综合考虑题目的难度、区分度等原因，没选到的题不一定就是简单题），就拿来做月赛了。简单写下方法：

A Beautiful Meadow

       这题是我出的，连通分量的dp。题目意思是找一条路，不能经过若干个点，让经过点的权值和最大。这种dp写起来很复杂，也有找一个圈的。大体思路却很简单，保留一行的状态。每个状态是由本行前若干列已经确定的加上上一行其他列确定过的（这样正好是一行）组成。把确定的和待确定的边界划一条线，每个格子要么是穿入边界（in）或者穿出边界(out)，注意起点和终点的状态比较特殊（head），或者是不在路径上(none)，这样4种状态，这样可以用bit压缩存储，存储使用2bit表示一个格子的状态，所以总状态需要2*7=14bit，可以接受。状态转化很复杂要想清楚。（就是自己左边的格子和上边的格子的状态可以基本决定本格子的状态了），特别是有时候要把in,out反向（注意in和out是配对的），我是直接用map保存的最大值的，估计自己