多米諾骨牌源碼

『壹』 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;}