真是個討厭的題目，輸出及其猥瑣。其他的點評，沒了。
#include<iostream>
#include<cmath>
using namespace std;
const int maxn=100020;
int v[maxn];
int order[maxn];
int ans[maxn];//存放結(jié)果
int solve(int n,int m,int &pos)
{
memset(order,0,sizeof(order));
memset(v,0,sizeof(v));
int f=0;
int cnt=0;
v[n]=1;n*=10;
while(n)
{
if(v[n%m]==1)
{
f=1;ans[++cnt]=n/m;n%=m;
break;
}
else v[n%m]=1;
ans[++cnt]=n/m;
n%=m;
order[n]=cnt;
n*=10;
}
if(f==0)
pos=-1;
else pos=order[n];
return cnt;
}
int get(int n)
{
return log((double)n);
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)!=EOF)
{
int cnt;
int pos;
if(n%m==0)
{
printf("%d.0\n",n/m);
continue;
}
int zhengshu=n/m;
n%=m;
int len=solve(n,m,pos);
if(zhengshu!=0)
cnt=get(zhengshu)+1;
else
cnt=2;
if(pos==-1)
{
printf("%d.",zhengshu);
for(int i=1;i<=len;i++)
{
printf("%d",ans[i]);
cnt++;
if(cnt%76==0)
printf("\n");
}
if(cnt%76!=0)
printf("\n");
}
else
{
printf("%d.",zhengshu);
for(int i=1;i<=pos;i++)
{
printf("%d",ans[i]);
cnt++;
if(cnt%76==0)
printf("\n");
}
printf("(");
cnt++;
if(cnt%76==0)
printf("\n");
for(int i=pos+1;i<=len;i++)
{
printf("%d",ans[i]);
cnt++;
if(cnt%76==0)
printf("\n");
}
printf(")");
cnt++;
if(cnt%76==0)
printf("\n");
if(cnt%76!=0)
printf("\n");
}
}
return 0;
}
世界的每一個角落，
都埋藏著對中國人的疑問。
路在問，樹在問，
窗后的眼睛都在問：
你們，究竟是什么人？
太長的歲月是否積累了太多的計謀？
太多的人口是否潛伏著威脅的可能？
你們是否爾虞我詐？
你們是否尊重人性？
我一次次講解，
一次次辯論，
他們總是禮貌地點頭，
卻又轉(zhuǎn)向了別的傳聞。
在遠(yuǎn)方的街道我曾暗暗自語：
既然人家不信，
那又何必傷心？
他們有他們的偏見，
我們有我們的毛病。
終于，
一次自然地震引發(fā)了精神地震，
一場驚世天災(zāi)掀去了遠(yuǎn)年蒙塵，
一條地殼裂縫透露了事實真相，
一批中國地名擦亮了世界的眼睛。
歷史上居然會有這樣一個時刻，
十幾億人的眼淚匯流成了一個愛字；
地球上居然會有這樣一個角落，
十幾億人的心思全在廢墟下的生命。
空前擁擠的天空，
空前擁擠的險徑，
空前奔涌的血液，
空前奔涌的呼聲，
全在表達(dá)著一種文明，
以及它延續(xù)至今的原因。
對于飛來橫禍，再驕傲的民族也很難作出一致的反應(yīng)，
對于生離死別，再高雅的人群也很難設(shè)計動人的表情。
那么，這次，
請看中國的反應(yīng)，中國的表情！
毫不預(yù)警下的透明呈現(xiàn)，
只能是中華民族的自然本性。
遠(yuǎn)方的朋友終于看清了吧？
這就是中國人。
在全民肅立的哀悼日我又暗暗自語：
如果能有十個輪回，
即使再有海嘯地震，
我已別無選擇，
永遠(yuǎn)在這里投生！
RT,突然感覺到人生面臨的巨大的危機感。我想，ACM這個東西，可能我需要告別你一段時間了，不過請相信我，我們還會再見面。
當(dāng)AH=0EH
這個子程序是使顯示器像打字機一樣的顯示字符來，在前面用 AH=09H/INT 10H 和 AH=0AH/INT 10H 都可以在螢光幕上顯示字符，但是這兩奘方式顯示字符之后，光標(biāo)位置并不移動，而 AH=0EH/INT 10H 則會使光標(biāo)位置移動，每顯示一個字符，光標(biāo)會往右移一格，假如已經(jīng)到最右邊了，則光標(biāo)會移到最左邊并移到下一列，假如已經(jīng)移到最下面一列的最右邊，則屏幕會向上卷動。
AL 寄存器存要顯示的字符，BH 為目前的顯示頁，如果是在圖形模式，則 BH 須設(shè)為 0，假如是在圖形模式下，也可以設(shè)定 BL 來表示文字的顏色，文字模式下的 BL 則無功能。
好像目前還沒有這方面題目的總結(jié)。這幾天連續(xù)看到四個問這類題目的人，今天在這里簡單寫一下。這里我們不介紹其它有關(guān)矩陣的知識，只介紹矩陣乘法和相關(guān)性質(zhì)。
不要以為數(shù)學(xué)中的矩陣也是黑色屏幕上不斷變化的綠色字符。在數(shù)學(xué)中，一個矩陣說穿了就是一個二維數(shù)組。一個n行m列的矩陣可以乘以一個m行p列的矩陣，得到的結(jié)果是一個n行p列的矩陣，其中的第i行第j列位置上的數(shù)等于前一個矩陣第i行上的m個數(shù)與后一個矩陣第j列上的m個數(shù)對應(yīng)相乘后所有m個乘積的和。比如，下面的算式表示一個2行2列的矩陣乘以2行3列的矩陣，其結(jié)果是一個2行3列的矩陣。其中，結(jié)果的那個4等于2*2+0*1：
下面的算式則是一個1 x 3的矩陣乘以3 x 2的矩陣，得到一個1 x 2的矩陣：
矩陣乘法的兩個重要性質(zhì)：一，矩陣乘法
不滿足交換律；二，矩陣乘法滿足結(jié)合律。為什么矩陣乘法不滿足交換律呢？廢話，交換過來后兩個矩陣有可能根本不能相乘。為什么它又滿足結(jié)合律呢？仔細(xì)想想你會發(fā)現(xiàn)這也是廢話。假設(shè)你有三個矩陣A、B、C，那么(AB)C和A(BC)的結(jié)果的第i行第j列上的數(shù)都等于所有A(ik)*B(kl)*C(lj)的和（枚舉所有的k和l）。
經(jīng)典題目1 給定n個點，m個操作，構(gòu)造O(m+n)的算法輸出m個操作后各點的位置。操作有平移、縮放、翻轉(zhuǎn)和旋轉(zhuǎn) 這里的操作是對所有點同時進(jìn)行的。其中翻轉(zhuǎn)是以坐標(biāo)軸為對稱軸進(jìn)行翻轉(zhuǎn)（兩種情況），旋轉(zhuǎn)則以原點為中心。如果對每個點分別進(jìn)行模擬，那么m個操作總共耗時O(mn)。利用矩陣乘法可以在O(m)的時間里把所有操作合并為一個矩陣，然后每個點與該矩陣相乘即可直接得出最終該點的位置，總共耗時O(m+n)。假設(shè)初始時某個點的坐標(biāo)為x和y，下面5個矩陣可以分別對其進(jìn)行平移、旋轉(zhuǎn)、翻轉(zhuǎn)和旋轉(zhuǎn)操作。預(yù)先把所有m個操作所對應(yīng)的矩陣全部乘起來，再乘以(x,y,1)，即可一步得出最終點的位置。
經(jīng)典題目2 給定矩陣A，請快速計算出A^n（n個A相乘）的結(jié)果，輸出的每個數(shù)都mod p。 由于矩陣乘法具有結(jié)合律，因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我們可以得到這樣的結(jié)論：當(dāng)n為偶數(shù)時，A^n = A^(n/2) * A^(n/2)；當(dāng)n為奇數(shù)時，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。這就告訴我們，計算A^n也可以使用二分快速求冪的方法。例如，為了算出A^25的值，我們只需要遞歸地計算出A^12、A^6、A^3的值即可。根據(jù)
這里的一些結(jié)果，我們可以在計算過程中不斷取模，避免高精度運算。
經(jīng)典題目3 POJ3233 (感謝
rmq)
題目大意：給定矩陣A，求A + A^2 + A^3 + ... + A^k的結(jié)果（兩個矩陣相加就是對應(yīng)位置分別相加）。輸出的數(shù)據(jù)mod m。k<=10^9。
這道題兩次二分，相當(dāng)經(jīng)典。首先我們知道，A^i可以二分求出。然后我們需要對整個題目的數(shù)據(jù)規(guī)模k進(jìn)行二分。比如，當(dāng)k=6時，有：
A + A^2 + A^3 + A^4 + A^5 + A^6 =
(A + A^2 + A^3) + A^3*
(A + A^2 + A^3) 應(yīng)用這個式子后，規(guī)模k減小了一半。我們二分求出A^3后再遞歸地計算A + A^2 + A^3，即可得到原問題的答案。
經(jīng)典題目4 VOJ1049 題目大意：順次給出m個置換，反復(fù)使用這m個置換對初始序列進(jìn)行操作，問k次置換后的序列。m<=10, k<2^31。
首先將這m個置換“合并”起來（算出這m個置換的乘積），然后接下來我們需要執(zhí)行這個置換k/m次（取整，若有余數(shù)則剩下幾步模擬即可）。注意任意一個置換都可以表示成矩陣的形式。例如，將1 2 3 4置換為3 1 2 4，相當(dāng)于下面的矩陣乘法：
置換k/m次就相當(dāng)于在前面乘以k/m個這樣的矩陣。我們可以二分計算出該矩陣的k/m次方，再乘以初始序列即可。做出來了別忙著高興，得意之時就是你滅亡之日，別忘了最后可能還有幾個置換需要模擬。
經(jīng)典題目5 《算法藝術(shù)與信息學(xué)競賽》207頁（2.1代數(shù)方法和模型，[例題5]細(xì)菌，版次不同可能頁碼有偏差） 大家自己去看看吧，書上講得很詳細(xì)。解題方法和上一題類似，都是用矩陣來表示操作，然后二分求最終狀態(tài)。
經(jīng)典題目6 給定n和p，求第n個Fibonacci數(shù)mod p的值，n不超過2^31 根據(jù)前面的一些思路，現(xiàn)在我們需要構(gòu)造一個2 x 2的矩陣，使得它乘以(a,b)得到的結(jié)果是(b,a+b)。每多乘一次這個矩陣，這兩個數(shù)就會多迭代一次。那么，我們把這個2 x 2的矩陣自乘n次，再乘以(0,1)就可以得到第n個Fibonacci數(shù)了。不用多想，這個2 x 2的矩陣很容易構(gòu)造出來：
經(jīng)典題目7 VOJ1067 我們可以用上面的方法二分求出任何一個線性遞推式的第n項，其對應(yīng)矩陣的構(gòu)造方法為：在右上角的(n-1)*(n-1)的小矩陣中的主對角線上填1，矩陣第n行填對應(yīng)的系數(shù)，其它地方都填0。例如，我們可以用下面的矩陣乘法來二分計算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k項：
利用矩陣乘法求解線性遞推關(guān)系的題目我能編出一卡車來。這里給出的例題是系數(shù)全為1的情況。
經(jīng)典題目8 給定一個有向圖，問從A點恰好走k步（允許重復(fù)經(jīng)過邊）到達(dá)B點的方案數(shù)mod p的值 把給定的圖轉(zhuǎn)為鄰接矩陣，即A(i,j)=1當(dāng)且僅當(dāng)存在一條邊i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，實際上就等于從點i到點j恰好經(jīng)過2條邊的路徑數(shù)（枚舉k為中轉(zhuǎn)點）。類似地，C*A的第i行第j列就表示從i到j(luò)經(jīng)過3條邊的路徑數(shù)。同理，如果要求經(jīng)過k步的路徑數(shù)，我們只需要二分求出A^k即可。
經(jīng)典題目9 用1 x 2的多米諾骨牌填滿M x N的矩形有多少種方案，M<=5，N<2^31，輸出答案mod p的結(jié)果 
我們以M=3為例進(jìn)行講解。假設(shè)我們把這個矩形橫著放在電腦屏幕上，從右往左一列一列地進(jìn)行填充。其中前n-2列已經(jīng)填滿了，第n-1列參差不齊。現(xiàn)在我們要做的事情是把第n-1列也填滿，將狀態(tài)轉(zhuǎn)移到第n列上去。由于第n-1列的狀態(tài)不一樣（有8種不同的狀態(tài)），因此我們需要分情況進(jìn)行討論。在圖中，我把轉(zhuǎn)移前8種不同的狀態(tài)放在左邊，轉(zhuǎn)移后8種不同的狀態(tài)放在右邊，左邊的某種狀態(tài)可以轉(zhuǎn)移到右邊的某種狀態(tài)就在它們之間連一根線。注意為了保證方案不重復(fù)，狀態(tài)轉(zhuǎn)移時我們不允許在第n-1列豎著放一個多米諾骨牌（例如左邊第2種狀態(tài)不能轉(zhuǎn)移到右邊第4種狀態(tài)），否則這將與另一種轉(zhuǎn)移前的狀態(tài)重復(fù)。把這8種狀態(tài)的轉(zhuǎn)移關(guān)系畫成一個有向圖，那么問題就變成了這樣：從狀態(tài)111出發(fā)，恰好經(jīng)過n步回到這個狀態(tài)有多少種方案。比如，n=2時有3種方案，111->011->111、111->110->111和111->000->111，這與用多米諾骨牌覆蓋3x2矩形的方案一一對應(yīng)。這樣這個題目就轉(zhuǎn)化為了我們前面的例題8。
后面我寫了一份此題的源代碼。你可以再次看到位運算的相關(guān)應(yīng)用。
經(jīng)典題目10 POJ2778 題目大意是，檢測所有可能的n位DNA串有多少個DNA串中不含有指定的病毒片段。合法的DNA只能由ACTG四個字符構(gòu)成。題目將給出10個以內(nèi)的病毒片段，每個片段長度不超過10。數(shù)據(jù)規(guī)模n<=2 000 000 000。
下面的講解中我們以ATC,AAA,GGC,CT這四個病毒片段為例，說明怎樣像上面的題一樣通過構(gòu)圖將問題轉(zhuǎn)化為例題8。我們找出所有病毒片段的前綴，把n位DNA分為以下7類：以AT結(jié)尾、以AA結(jié)尾、以GG結(jié)尾、以?A結(jié)尾、以?G結(jié)尾、以?C結(jié)尾和以??結(jié)尾。其中問號表示“其它情況”，它可以是任一字母，只要這個字母不會讓它所在的串成為某個病毒的前綴。顯然，這些分類是全集的一個劃分（交集為空，并集為全集）。現(xiàn)在，假如我們已經(jīng)知道了長度為n-1的各類DNA中符合要求的DNA個數(shù)，我們需要求出長度為n時各類DNA的個數(shù)。我們可以根據(jù)各類型間的轉(zhuǎn)移構(gòu)造一個邊上帶權(quán)的有向圖。例如，從AT不能轉(zhuǎn)移到AA，從AT轉(zhuǎn)移到??有4種方法（后面加任一字母），從?A轉(zhuǎn)移到AA有1種方案（后面加個A），從?A轉(zhuǎn)移到??有2種方案（后面加G或C），從GG到??有2種方案（后面加C將構(gòu)成病毒片段，不合法，只能加A和T）等等。這個圖的構(gòu)造過程類似于用有限狀態(tài)自動機做串匹配。然后，我們就把這個圖轉(zhuǎn)化成矩陣，讓這個矩陣自乘n次即可。最后輸出的是從??狀態(tài)到所有其它狀態(tài)的路徑數(shù)總和。
題目中的數(shù)據(jù)規(guī)模保證前綴數(shù)不超過100，一次矩陣乘法是三方的，一共要乘log(n)次。因此這題總的復(fù)雜度是100^3 * log(n)，AC了。
最后給出第9題的代碼供大家參考（今天寫的，熟悉了一下C++的類和運算符重載）。為了避免大家看代碼看著看著就忘了，我把這句話放在前面來說：
Matrix67原創(chuàng)，轉(zhuǎn)貼請注明出處。
#include <cstdio>
#define SIZE (1<<m)
#define MAX_SIZE 32
using namespace std;
class CMatrix
{
public:
long element[MAX_SIZE][MAX_SIZE];
void setSize(int);
void setModulo(int);
CMatrix operator* (CMatrix);
CMatrix power(int);
private:
int size;
long modulo;
};
void CMatrix::setSize(int a)
{
for (int i=0; i<a; i++)
for (int j=0; j<a; j++)
element[i][j]=0;
size = a;
}
void CMatrix::setModulo(int a)
{
modulo = a;
}
CMatrix CMatrix::operator* (CMatrix param)
{
CMatrix product;
product.setSize(size);
product.setModulo(modulo);
for (int i=0; i<size; i++)
for (int j=0; j<size; j++)
for (int k=0; k<size; k++)
{
product.element[i][j]+=element[i][k]*param.element[k][j];
product.element[i][j]%=modulo;
}
return product;
}
CMatrix CMatrix::power(int exp)
{
CMatrix tmp = (*this) * (*this);
if (exp==1) return *this;
else if (exp & 1) return tmp.power(exp/2) * (*this);
else return tmp.power(exp/2);
}
int main()
{
const int validSet[]={0,3,6,12,15,24,27,30};
long n, m, p;
CMatrix unit;
scanf("%d%d%d", &n, &m, &p);
unit.setSize(SIZE);
for(int i=0; i<SIZE; i++)
for(int j=0; j<SIZE; j++)
if( ((~i)&j) == ((~i)&(SIZE-1)) )
{
bool isValid=false;
for (int k=0; k<8; k++)isValid=isValid||(i&j)==validSet[k];
unit.element[i][j]=isValid;
}
unit.setModulo(p);
printf("%d", unit.power(n).element[SIZE-1][SIZE-1] );
return 0;
} 源地址：
http://www.matrix67.com/blog/?s=%E5%8D%81%E4%B8%AA%E5%88%A9%E7%94%A8%E7%9F%A9%E9%98%B5%E4%B9%98%E6%B3%95%E8%A7%A3%E5%86%B3%E7%9A%84%E7%BB%8F%E5%85%B8%E9%A2%98%E7%9B%AE
摘要: 沒想到這個暴力題讓我郁悶了半小時，最后發(fā)現(xiàn)原來是回溯的問題。基本功不扎實啊。。。
#include<iostream>#include<cstring>using namespace std;int n;int v[200];int order[200];struct node{ ...
閱讀全文
題意：P(x)=x各個數(shù)字位的乘積。x<=10^1000，求min{ans|ans>x && P(ans)=P(x)}。
顯然如果x的數(shù)字位含有0，分兩種情況：
1）：只有一個0，如果0在個位數(shù)，那么x+10就是最優(yōu)解了。如果0不在個位數(shù)，則x+1就是最優(yōu)解。
2）：有2個或2個以上的0，那么x+1就是最優(yōu)解。
證明略，很容易看出的。
接下來就是處理不含0的情況。
把x的各個數(shù)字位分解質(zhì)因子。只有2,3,5,7這4個素數(shù)。
然后從高位深搜解，這里有加些剪枝。就是在搜索的時候每步都有保證搜到的解>=x。這樣的話就會很快的搜到最優(yōu)解。具體實現(xiàn)就是設(shè)一個flag值，flag為真表示當(dāng)前搜的解>x否則=x。如果flag為真，則改數(shù)字位從1開始搜到9，如果flag不為真，則改狀態(tài)的數(shù)字位從x原本的數(shù)字位開始搜，只要碰到改狀態(tài)的數(shù)字大于原本的數(shù)字位就要改flag為真。這樣就可以保證比較快的搜到解了。然后隨便在了點雜七雜八的剪枝就差不多了。
最后還要在判斷剛才的搜索有沒有找到解，如果沒有找到解，那么只剩一種情況了，就是增加一個數(shù)字位'1'；排序，輸出。
我的搜索已經(jīng)寫的很暴力了，str函數(shù)狂用，用時10ms。
不知道有沒有更高效的做法，或者有直接更妙的構(gòu)造方法呢？
——by yayamao
先看費馬小定理：
費馬小定理是
數(shù)論中的一個重要定理,其內(nèi)容為:
假如p是質(zhì)數(shù)，且(a,p)=1，那么 a^(p-1) ≡１（mod p）
假如p是質(zhì)數(shù)，且a,p互質(zhì)，那么 a的(p-1)次方除以p的余數(shù)恒等于1
逆元：
設(shè)m為正整數(shù)，a為正整數(shù)，如果存在a' 使得：
a X a' = 1（mod m）
a'叫做a的逆元。密碼學(xué)中用到了這個結(jié)論。RSA.
證明:x^(MOD-1) = 1 (mod MOD)
x*x^(MOD-2) = 1 (mod MOD) x^(MOD-2)為其逆元
其中MOD 為素數(shù) ， x要小于MOD,如果x>=MOD,可以先對x取MOD,這不會影響結(jié)果。
另一種想法：
其實用莫線性方程解a'亦可。 擴展歐幾里德...
摘要: 就是寫得太長了 可以更精簡些的
#include <iostream> using namespace std; class CFraction { private: &nbs...
閱讀全文