青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

The Fourth Dimension Space

枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

十個利用矩陣乘法解決的經典題目(matrix67)

好像目前還沒有這方面題目的總結。這幾天連續看到四個問這類題目的人,今天在這里簡單寫一下。這里我們不介紹其它有關矩陣的知識,只介紹矩陣乘法和相關性質。
    不要以為數學中的矩陣也是黑色屏幕上不斷變化的綠色字符。在數學中,一個矩陣說穿了就是一個二維數組。一個n行m列的矩陣可以乘以一個m行p列的矩陣,得到的結果是一個n行p列的矩陣,其中的第i行第j列位置上的數等于前一個矩陣第i行上的m個數與后一個矩陣第j列上的m個數對應相乘后所有m個乘積的和。比如,下面的算式表示一個2行2列的矩陣乘以2行3列的矩陣,其結果是一個2行3列的矩陣。其中,結果的那個4等于2*2+0*1:
    
    下面的算式則是一個1 x 3的矩陣乘以3 x 2的矩陣,得到一個1 x 2的矩陣:
    

    矩陣乘法的兩個重要性質:一,矩陣乘法不滿足交換律;二,矩陣乘法滿足結合律。為什么矩陣乘法不滿足交換律呢?廢話,交換過來后兩個矩陣有可能根本不能相乘。為什么它又滿足結合律呢?仔細想想你會發現這也是廢話。假設你有三個矩陣A、B、C,那么(AB)C和A(BC)的結果的第i行第j列上的數都等于所有A(ik)*B(kl)*C(lj)的和(枚舉所有的k和l)。

經典題目1 給定n個點,m個操作,構造O(m+n)的算法輸出m個操作后各點的位置。操作有平移、縮放、翻轉和旋轉
    這里的操作是對所有點同時進行的。其中翻轉是以坐標軸為對稱軸進行翻轉(兩種情況),旋轉則以原點為中心。如果對每個點分別進行模擬,那么m個操作總共耗時O(mn)。利用矩陣乘法可以在O(m)的時間里把所有操作合并為一個矩陣,然后每個點與該矩陣相乘即可直接得出最終該點的位置,總共耗時O(m+n)。假設初始時某個點的坐標為x和y,下面5個矩陣可以分別對其進行平移、旋轉、翻轉和旋轉操作。預先把所有m個操作所對應的矩陣全部乘起來,再乘以(x,y,1),即可一步得出最終點的位置。
    

經典題目2 給定矩陣A,請快速計算出A^n(n個A相乘)的結果,輸出的每個數都mod p。
    由于矩陣乘法具有結合律,因此A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我們可以得到這樣的結論:當n為偶數時,A^n = A^(n/2) * A^(n/2);當n為奇數時,A^n = A^(n/2) * A^(n/2) * A (其中n/2取整)。這就告訴我們,計算A^n也可以使用二分快速求冪的方法。例如,為了算出A^25的值,我們只需要遞歸地計算出A^12、A^6、A^3的值即可。根據這里的一些結果,我們可以在計算過程中不斷取模,避免高精度運算。

經典題目3 POJ3233 (感謝rmq)
    題目大意:給定矩陣A,求A + A^2 + A^3 + ... + A^k的結果(兩個矩陣相加就是對應位置分別相加)。輸出的數據mod m。k<=10^9。
    這道題兩次二分,相當經典。首先我們知道,A^i可以二分求出。然后我們需要對整個題目的數據規模k進行二分。比如,當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)
    應用這個式子后,規模k減小了一半。我們二分求出A^3后再遞歸地計算A + A^2 + A^3,即可得到原問題的答案。

經典題目4 VOJ1049
    題目大意:順次給出m個置換,反復使用這m個置換對初始序列進行操作,問k次置換后的序列。m<=10, k<2^31。
    首先將這m個置換“合并”起來(算出這m個置換的乘積),然后接下來我們需要執行這個置換k/m次(取整,若有余數則剩下幾步模擬即可)。注意任意一個置換都可以表示成矩陣的形式。例如,將1 2 3 4置換為3 1 2 4,相當于下面的矩陣乘法:
    
    置換k/m次就相當于在前面乘以k/m個這樣的矩陣。我們可以二分計算出該矩陣的k/m次方,再乘以初始序列即可。做出來了別忙著高興,得意之時就是你滅亡之日,別忘了最后可能還有幾個置換需要模擬。

經典題目5 《算法藝術與信息學競賽》207頁(2.1代數方法和模型,[例題5]細菌,版次不同可能頁碼有偏差)
    大家自己去看看吧,書上講得很詳細。解題方法和上一題類似,都是用矩陣來表示操作,然后二分求最終狀態。

經典題目6 給定n和p,求第n個Fibonacci數mod p的值,n不超過2^31
    根據前面的一些思路,現在我們需要構造一個2 x 2的矩陣,使得它乘以(a,b)得到的結果是(b,a+b)。每多乘一次這個矩陣,這兩個數就會多迭代一次。那么,我們把這個2 x 2的矩陣自乘n次,再乘以(0,1)就可以得到第n個Fibonacci數了。不用多想,這個2 x 2的矩陣很容易構造出來:
    

經典題目7 VOJ1067
    我們可以用上面的方法二分求出任何一個線性遞推式的第n項,其對應矩陣的構造方法為:在右上角的(n-1)*(n-1)的小矩陣中的主對角線上填1,矩陣第n行填對應的系數,其它地方都填0。例如,我們可以用下面的矩陣乘法來二分計算f(n) = 4f(n-1) - 3f(n-2) + 2f(n-4)的第k項:
    
    利用矩陣乘法求解線性遞推關系的題目我能編出一卡車來。這里給出的例題是系數全為1的情況。

經典題目8 給定一個有向圖,問從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即可。

經典題目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>
#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

posted on 2010-04-18 16:46 abilitytao 閱讀(677) 評論(0)  編輯 收藏 引用

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            国内精品久久国产| 欧美乱妇高清无乱码| 国产欧美日韩亚洲精品| 欧美在线免费观看视频| 欧美一级日韩一级| 亚洲第一黄网| 亚洲精品国产视频| 亚洲高清123| 一本久道综合久久精品| 在线午夜精品自拍| 国产亚洲制服色| 欧美国产欧美亚洲国产日韩mv天天看完整| 国产一区二区高清视频| 一区二区日韩精品| 亚洲欧美国产精品va在线观看 | 亚洲国产天堂久久综合网| 欧美久久久久久蜜桃| 亚洲欧美日韩国产成人精品影院| 亚洲欧美精品伊人久久| 亚洲品质自拍| 亚洲在线观看免费视频| 亚洲高清av在线| 亚洲综合好骚| 亚洲六月丁香色婷婷综合久久| 一区二区三区回区在观看免费视频| 国产精品视频一区二区三区| 欧美激情性爽国产精品17p| 国产精品久久久久久av福利软件| 久久亚洲私人国产精品va媚药| 欧美精品免费在线| 久久国产天堂福利天堂| 欧美精品啪啪| 欧美高清视频一区| 国产一区日韩欧美| 国产精品99久久久久久久vr| 91久久国产自产拍夜夜嗨| 亚洲综合色视频| 一区二区高清| 欧美www视频| 麻豆成人在线| 国产欧美日本一区二区三区| 亚洲黄色成人| 91久久精品一区二区别| 久久精品最新地址| 欧美主播一区二区三区| 欧美视频一区二区三区…| 美女精品网站| 伊人狠狠色j香婷婷综合| 亚洲欧美综合一区| 欧美一区二粉嫩精品国产一线天| 欧美激情在线| 亚洲国产欧美一区| 亚洲无线视频| 久久一区二区精品| 午夜久久tv| 国产精品成人一区二区| 亚洲乱码久久| 99精品国产福利在线观看免费 | 午夜精彩视频在线观看不卡| 欧美激情中文字幕乱码免费| 欧美福利一区二区三区| 激情综合电影网| 另类图片国产| 欧美激情一区在线观看| 亚洲激情一区| 亚洲欧美不卡| 欧美成人综合网站| 免费在线看成人av| 国产嫩草一区二区三区在线观看| 亚洲精品一区中文| 亚洲免费精彩视频| 欧美日韩精品免费观看视频| 91久久午夜| 一区二区冒白浆视频| 欧美日韩一区二| av成人激情| 性色av香蕉一区二区| 国产精品夜夜夜一区二区三区尤| 亚洲一区免费| 久久久久久久久岛国免费| 激情欧美亚洲| 欧美人与禽性xxxxx杂性| 一区二区三区色| 久久精品国产综合精品| 在线观看成人小视频| 农村妇女精品| 一区二区三区日韩精品| 久久av资源网站| 亚洲国产乱码最新视频| 欧美日韩亚洲国产精品| 亚洲欧美日韩爽爽影院| 欧美激情在线播放| 欧美一区二视频| 在线观看亚洲精品| 国产精品电影在线观看| 久久色在线播放| 日韩视频免费观看| 久久久久久噜噜噜久久久精品| …久久精品99久久香蕉国产| 欧美日韩91| 久久精品三级| 中文日韩欧美| 欧美国产一区在线| 欧美在线播放| 一个色综合导航| 在线观看精品| 国产精品热久久久久夜色精品三区 | 可以看av的网站久久看| 亚洲综合精品自拍| 亚洲三级毛片| 老司机免费视频一区二区三区| 一区二区三区www| 精品动漫一区| 国产精品制服诱惑| 欧美另类人妖| 久久亚洲精品欧美| 欧美在线视频一区| 亚洲综合视频一区| 99精品视频免费观看视频| 欧美成人嫩草网站| 久久先锋影音av| 久久久久久一区二区三区| 亚洲一区免费网站| 亚洲久色影视| 亚洲国产日韩一区二区| 黄色另类av| 国产亚洲网站| 国产一区二区三区高清播放| 国产精品萝li| 欧美婷婷六月丁香综合色| 欧美男人的天堂| 欧美激情中文字幕在线| 欧美激情一区二区三区在线视频| 久久精品亚洲| 免费在线观看成人av| 久久看片网站| 久色婷婷小香蕉久久| 久久久青草青青国产亚洲免观| 香蕉久久精品日日躁夜夜躁| 亚洲愉拍自拍另类高清精品| 亚洲视频免费在线观看| 亚洲一区二区在| 亚洲欧美精品在线| 午夜在线观看免费一区| 欧美一区在线直播| 久久久精品午夜少妇| 久久久国产精品一区二区三区| 欧美在线观看一区二区| 久久婷婷av| 免费影视亚洲| 亚洲国产小视频在线观看| 亚洲精一区二区三区| 中文欧美日韩| 久久国产精品一区二区三区| 久久本道综合色狠狠五月| 久久久国产精品亚洲一区| 欧美成人免费播放| 欧美日韩国产色综合一二三四| 欧美日韩一区精品| 国产亚洲一区二区在线观看 | 国产精品久久久久久久久久久久 | 亚洲免费在线视频| 久久久久久久97| 欧美大片国产精品| 亚洲乱码国产乱码精品精可以看| 亚洲午夜高清视频| 久久国产精品久久w女人spa| 免费欧美电影| 国产精品美女xx| 亚洲国产精品传媒在线观看| 在线一区二区三区做爰视频网站| 一本色道久久综合| 一区二区三区久久久| 日韩一级黄色片| 欧美大片免费久久精品三p| 国产精品成人国产乱一区| 麻豆精品视频| 国产精品播放| 亚洲成人在线网站| 亚洲欧美成人网| 久热精品在线视频| 在线一区二区三区四区五区| 欧美中文字幕不卡| 欧美日韩一级黄| 亚洲福利在线看| 欧美与欧洲交xxxx免费观看 | 亚洲天堂av图片| 蜜乳av另类精品一区二区| 亚洲视频一区二区| 免费久久99精品国产自| 国产在线不卡精品| 亚洲免费影院| 亚洲成人在线网站| 久久精品中文字幕一区二区三区| 国产精品hd| 一二三四社区欧美黄| 欧美国产视频日韩| 久久国产高清| 国产一区二区三区在线观看精品 | 亚洲国产精品视频一区|