多米诺骨牌源码

‘壹’ free Pascal程序 高手进~

由于我自己测试时数据太大，所以我都除了12345，你可以把mod12345去掉就可以了 （我不知道什么是生成树）
第一题
var
a,b:array[0..1000]of longint;
i,n:longint;
begin
a[1]:=8;
b[1]:=1;
readln(n);
if n=1 then writeln(1)
else
begin
for i:=2 to n do
begin
a[i]:=(9*a[i-1]+b[i-1]) mod 12345;
b[i]:=(9*b[i-1]+a[i-1]) mod 12345;
end;
writeln(a[n]);
end;
end.

第二题
program p1399;
var
i,j,k,t,n:longint;
a:array[0..1000] of longint;
begin
readln(n);
a[1]:=1;
a[0]:=1;
for i:=2 to n do
a[i]:=(a[i-2]*2+a[i-1]) mod 12345;
writeln(a[n]);
end.

第三题
program p1400;
var
a:array[0..1000]of longint;
i,n:longint;
begin
a[0]:=1;
a[1]:=3;
readln(n);
for i:=2 to n do a[i]:=(a[i-1]*2+a[i-2])mod 12345;
writeln(a[n]);
end.

第四题
var
a:array[0..1000]of longint;
i,n,k:longint;
begin

a[0]:=1;
a[1]:=1;
readln(n);
for i:=2 to n do
begin
for k:=0 to i-2 do
a[i]:=(a[i]+a[k]*a[i-2-k])mod 12345;
a[i]:=(a[i]+a[i-1]) mod 12345;
end;
writeln(a[n]);

end.

‘贰’ 为什么黑莓在美国本被封杀为什么黑莓就连政府都具性它的网络

由于美国总统奥巴马用的是黑莓手机，许多人曾误以为RIM是美国公司，其实RIM是加拿大公司。不过现在连卖茶叶蛋的都知道RIM不会是美国公司，道理很简单：如果黑莓手机真是美国的，哪有这么多国家敢宣布封杀它？2010年，庚寅年，黑莓流年不利。今年全世界都知道有个叫“黑莓”的倒霉蛋，它一不小心推倒了多米诺骨牌，阿联酋、沙特阿拉伯、印度、黎巴嫩、阿尔及利亚和印度尼西亚等国家都在计划封杀它，理由是担忧黑莓手机的安全性。不是因为它不安全，而是因为它太安全，安全到政府部门都无法监控，所以各国政府勒令RIM公司(黑莓服务商)开放加密信息，否则禁止使用。黑莓手机的遭遇告诉我们，社会是复杂的，现实是很搞的。你做得不好，你会倒霉，你做得太好，还是会倒霉。有段时间流行用东方文化来改造现代管理思想，看来不是没有道理。中国文化就讲究中庸之道，你不能不创新，又不能太创新；你不能不优秀，又不能太优秀；你不能不安全，又不能太安全。黑莓错就错在加密系统太安全了。黑莓手机的主要市场是在欧美，亚洲用户对它相对陌生。近两年前奥巴马握着黑莓手机入主白宫，成为美国历史上第一位在任期间使用手机的总统。由于美国总统的这个免费广告，许多人曾误以为RIM是美国公司，其实RIM是加拿大公司。不过现在连卖茶叶蛋的都知道这个倒霉蛋不会是美国公司，道理很简单：如果黑莓手机真是美国的，哪有这么多国家敢宣布封杀它？你听说过世界各国警告英特尔、微软或者谷歌：不开放源代码或核心技术就封杀吗？要说影响国家安全，RIM哪能比得过这些美国大佬！黑莓手机的第一个错是它太安全了，第二个错是它没有生在美国，第三个错是它的命不好。所谓“命不好”就是指莫名其妙的点背，比如黑莓；而所谓“命好”就是指毫无道理的走运，比如iPhone。苹果i-Phone在国际黑客大会上被人仅用20秒钟就攻破，平时开机都没这么快。而现在的媒体都在报道，由于iPhone安全易用，许多企业开始采购iPhone用于商务办公，苹果逐步从黑莓的企业用户中抢下市场份额。20秒就能被攻破的iPhone势如破竹，各国安全部门束手无策的黑莓却遭封杀，对此RIM只能仰天长叹：这叫什么世道！一个月前，《IT时报》记者采访了着名黑客克里斯·佩吉特，就是那位能随意监听GSM手机通话、嘲笑“GSM网应该被关闭”的哥们，他对苹果看不上眼，但非常赞赏黑莓的安全设置。世人都说苹果好，能为黑莓说句公道话的只剩下黑客了，大概是因为大家都姓“黑”吧。

‘叁’ 多米诺骨牌 pascal

[例5] 多米诺骨牌（DOMINO）问题描述：有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：顶行骨牌的点数之和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。对于上面这个例子，我们只需翻转最后一个骨牌，就可以使得顶行和底行的差值为0，所以例子的答案为1。解决问题：例子的上下部分之差是6+1+1+1-（1+5+3+2）=（6-1）+（1-5）+（1-3）+（1-2）=-2，而翻转最后一个骨牌后，上下之差变为（6-1）+（1-5）+（1-3）+（2-1）=0。由此看出，一个骨牌对翻转策略造成影响的是上下两数之差，骨牌上的数则是次要的了。这么一来，便把骨牌的放置状态由8个数字变为4个： 5 -4 -2 -1，翻转时只需取该位数字的相反数就行了。在本题中，因为各骨牌的翻转顺序没有限定，所以不能按骨牌编号作为阶段来划分。怎么办呢？考虑到隐含阶段类型的问题可以按状态最优值的大小来划分阶段。于是，我们以骨牌序列上下两部分的差值I作为状态，把达到这一状态的翻转步数作为状态值，记为f（I）。便有f（I）=min{f（I+j）+1} （-12〈=j<=12,j为偶数，且要求当前状态有差值为j/2的骨牌）。这里，I不是无限增大或减小，其范围取决于初始骨牌序列的数字差的和的大小。具体动态规划时，如例题，我们以f（-2）=0起步，根据骨牌状态，进行一次翻转，可得到f（-12）=1，f（6）=1，f（2）=1，f（0）=1，由于出现了f（0），因此程序便可以结束，否则将根据四个新状态继续扩展，直至出现f（0）或者无法生成新状态为止。注意：在各状态，除记录最少步数外，还需记录到达这一状态时各骨牌的放置情况；而当到达某一状态发现已记录有一种翻转策略时，则取步数较小的一种。 by 方奇（IOI2000论文集）

‘肆’ 矩阵乘法的经典题目

VOJ1067
我们可以用上面的方法二分求出任何一个线性递推式的第n项，其对应矩阵的构造方法为：在右上角的(n-1)*(n-1)的小矩阵中的主对角线上填1，矩阵第n行填对应的系数，其它地方都填0。例如，我们可以用下面的矩阵乘法来二分计算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k项：
利用矩阵乘法求解线性递推关系的题目我能编出一卡车来。这里给出的例题是系数全为1的情况。
给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可。 #include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#defineN10usingnamespacestd;constintmod=7777777;typedeflonglongLL;structmatrix{LLa[10][10];}origin;intn,m;matrixmultiply(matrixx,matrixy){matrixtemp;memset(temp.a,0,sizeof(temp.a));for(inti=0;i<n;i++){for(intj=0;j<n;j++){for(intk=0;k<n;k++){temp.a[i][j]+=x.a[i][k]*y.a[k][j];temp.a[i][j]=(temp.a[i][j])%mod;}}}returntemp;}matrixmatmod(matrixA,intk){matrixres;memset(res.a,0,sizeofres.a);for(inti=0;i<n;i++)res.a[i][i]=1;while(k){if(k&1)res=multiply(res,A);k>>=1;A=multiply(A,A);}returnres;}voidprint(matrixx){for(inti=0;i<n;i++){for(intj=0;j<n;j++)cout<<<<x.a[i][j];puts();}printf(--------------- );}intmain(){intk;while(cin>>n>>k){memset(origin.a,0,sizeoforigin.a);origin.a[0][0]=1;for(inti=1;i<=n;i++){origin.a[i][0]=1;for(intj=0;j<i;j++){origin.a[i][0]+=origin.a[j][0];}}//print(origin);matrixres;memset(res.a,0,sizeofres.a);for(inti=0;i<n-1;i++){res.a[i][i+1]=1;}for(inti=0;i<n;i++)res.a[n-1][i]=1;//print(res);res=matmod(res,k-1);LLfans=0;for(inti=0;i<n;i++){fans+=res.a[0][i]*origin.a[i][0];fans%=mod;}cout<<fans<<endl;}return0;}经典题目9
用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案，M<=5，N<2^31，输出答案mod p的结果
我们以M=3为例进行讲解。假设我们把这个矩形横着放在电脑屏幕上，从右往左一列一列地进行填充。其中前n-2列已经填满了，第n-1列参差不齐。现在我们要做的事情是把第n-1列也填满，将状态转移到第n列上去。由于第n-1列的状态不一样（有8种不同的状态），因此我们需要分情况进行讨论。在图中，我把转移前8种不同的状态放在左边，转移后8种不同的状态放在右边，左边的某种状态可以转移到右边的某种状态就在它们之间连一根线。注意为了保证方案不重复，状态转移时我们不允许在第n-1列竖着放一个多米诺骨牌（例如左边第2种状态不能转移到右边第4种状态），否则这将与另一种转移前的状态重复。把这8种状态的转移关系画成一个有向图，那么问题就变成了这样：从状态111出发，恰好经过n步回到这个状态有多少种方案。比如，n=2时有3种方案，111->011->111、111->110->111和111->000->111，这与用多米诺骨牌覆盖3x2矩形的方案一一对应。这样这个题目就转化为了我们前面的例题8。
后面我写了一份此题的源代码。你可以再次看到位运算的相关应用。
经典题目10
POJ2778
题目大意是，检测所有可能的n位DNA串有多少个DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四个字符构成。题目将给出10个以内的病毒片段，每个片段长度不超过10。数据规模n<=2 000 000 000。
下面的讲解中我们以ATC,AAA,GGC,CT这四个病毒片段为例，说明怎样像上面的题一样通过构图将问题转化为例题8。我们找出所有病毒片段的前缀，把n位DNA分为以下7类：以AT结尾、以AA结尾、以GG结尾、以?A结尾、以?G结尾、以?C结尾和以??结尾。其中问号表示“其它情况”，它可以是任一字母，只要这个字母不会让它所在的串成为某个病毒的前缀。显然，这些分类是全集的一个划分（交集为空，并集为全集）。现在，假如我们已经知道了长度为n-1的各类DNA中符合要求的DNA个数，我们需要求出长度为n时各类DNA的个数。我们可以根据各类型间的转移构造一个边上带权的有向图。例如，从AT不能转移到AA，从AT转移到??有4种方法（后面加任一字母），从?A转移到AA有1种方案（后面加个A），从?A转移到??有2种方案（后面加G或C），从GG到??有2种方案（后面加C将构成病毒片段，不合法，只能加A和T）等等。这个图的构造过程类似于用有限状态自动机做串匹配。然后，我们就把这个图转化成矩阵，让这个矩阵自乘n次即可。最后输出的是从??状态到所有其它状态的路径数总和。
题目中的数据规模保证前缀数不超过100，一次矩阵乘法是三方的，一共要乘log(n)次。因此这题总的复杂度是100^3 * log(n)，AC了。
最后给出第9题的代码供大家参考（今天写的，熟悉了一下C++的类和运算符重载）。为了避免大家看代码看着看着就忘了，我把这句话放在前面来说：
Matrix67原创，转贴请注明出处。 #include<cstdio>#defineSIZE(1<<m)#defineMAX_SIZE32usingnamespacestd;classCMatrix{public:longelement[MAX_SIZE][MAX_SIZE];voidsetSize(int);voidsetMolo(int);CMatrixoperator*(CMatrix);CMatrixpower(int);private:intsize;longmolo;};voidCMatrix::setSize(inta){for(inti=0;i<a;i++)for(intj=0;j<a;j++)element[i][j]=0;size=a;}voidCMatrix::setMolo(inta){molo=a;}CMatrixCMatrix::operator*(CMatrixparam){CMatrixproct;proct.setSize(size);proct.setMolo(molo);for(inti=0;i<size;i++)for(intj=0;j<size;j++)for(intk=0;k<size;k++){proct.element[i][j]+=element[i][k]*param.element[k][j];proct.element[i][j]%=molo;}returnproct;}CMatrixCMatrix::power(intexp){CMatrixtmp=(*this)*(*this);if(exp==1)return*this;elseif(exp&1)returntmp.power(exp/2)*(*this);elsereturntmp.power(exp/2);}intmain(){constintvalidSet[]={0,3,6,12,15,24,27,30};longn,m,p;CMatrixunit;scanf(%d%d%d,&n,&m,&p);unit.setSize(SIZE);for(inti=0;i<SIZE;i++)for(intj=0;j<SIZE;j++)if(((~i)&j)==((~i)&(SIZE-1))){boolisValid=false;for(intk=0;k<8;k++)isValid=isValid||(i&j)==validSet[k];unit.element[i][j]=isValid;}unit.setMolo(p);printf(%d,unit.power(n).element[SIZE-1][SIZE-1]);return0;}