• <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>
            經(jīng)典題型。如果列數(shù)較少,就能用我們熟知的狀態(tài)壓縮DP解決。但現(xiàn)在列數(shù)有231??紤]到相鄰兩列之間狀態(tài)轉(zhuǎn)移規(guī)則是相同的,我們可以用矩陣表示這種轉(zhuǎn)移規(guī)則,而最后的結(jié)果就是求這個(gè)轉(zhuǎn)移矩陣的n次冪的左上角元素。


            /*************************************************************************
            Author: WHU_GCC
            Created Time: 2007-10-6 11:05:55
            File Name: pku3420.cpp
            Description: 
            ***********************************************************************
            */

            #include 
            <iostream>
            using namespace std;
            #define out(x) (cout<<#x<<": "<<x<<endl)
            const int maxint=0x7FFFFFFF;
            typedef 
            long long int64;
            const int64 maxint64 = 0x7FFFFFFFFFFFFFFFLL;
            template
            <class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
            template
            <class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}

            int g[16][16];
            int M;

            void dfs(int old_state, int now, int new_state)
            {
                
            if (now > 3)
                
            {
                    g[old_state][new_state]
            ++;
                    
            return;
                }

                
            if (old_state & (1 << now))
                    dfs(old_state, now 
            + 1, new_state);
                
            if (now <= 2)
                
            {
                    
            if ((old_state & (1 << now)) == 0 && (old_state & (1 << (now + 1))) == 0)
                        dfs(old_state, now 
            + 2, new_state);
                }

                
            if ((old_state & (1 << now)) == 0)
                    dfs(old_state, now 
            + 1, new_state | (1 << now));
            }


            void mul(int a[16][16], int b[16][16], int c[16][16])
            {
                
            for (int i = 0; i < 16; i++)
                    
            for (int j = 0; j < 16; j++)
                    
            {
                        c[i][j] 
            = 0;
                        
            for (int k = 0; k < 16; k++)
                            c[i][j] 
            += a[i][k] * b[k][j];
                        c[i][j] 
            %= M;
                    }

            }


            int calc(int n)
            {
                
            int p[16][16];
                memcpy(p, g, 
            sizeof(p));
                
                
            int ans[16][16], tmp[16][16];
                memset(ans, 
            0sizeof(ans));
                
            for (int i = 0; i < 16; i++)
                    ans[i][i] 
            = 1;

                
            while (n)
                
            {
                    
            if (n & 1)
                    
            {
                        mul(ans, p, tmp);
                        memcpy(ans, tmp, 
            sizeof(tmp));
                    }

                    n 
            >>= 1;
                    mul(p, p, tmp);
                    memcpy(p, tmp, 
            sizeof(tmp));
                }

                
            return ans[0][0];
            }


            int main()
            {
                memset(g, 
            0sizeof(g));
                
            for (int i = 0; i < 16; i++)
                    dfs(i, 
            00);
                
                
            int n;
                
            while (scanf("%d%d"&n, &M), n + M != 0)
                
            {
                    printf(
            "%d\n", calc(n));
                }

                
            return 0;
            }
            posted on 2007-10-08 09:19 Felicia 閱讀(1126) 評(píng)論(0)  編輯 收藏 引用 所屬分類: 動(dòng)態(tài)規(guī)劃
             
            深夜久久AAAAA级毛片免费看| 久久成人精品视频| 日韩人妻无码一区二区三区久久99| 97精品伊人久久大香线蕉app| 国产A级毛片久久久精品毛片| 囯产极品美女高潮无套久久久| 久久久久亚洲AV无码观看| 日韩va亚洲va欧美va久久| 国产A三级久久精品| 久久99中文字幕久久| 国内精品伊人久久久久妇| 蜜桃麻豆www久久| 久久综合综合久久综合| 国内精品久久久久久久涩爱| 国产成人久久AV免费| 久久中文字幕视频、最近更新| 亚洲精品国产字幕久久不卡| 四虎国产精品免费久久久| 伊人久久大香线焦AV综合影院 | 日本三级久久网| 精品免费久久久久久久| 久久人人爽爽爽人久久久| 日本人妻丰满熟妇久久久久久| 久久久久免费视频| 国产精品欧美久久久久无广告 | 欧美午夜A∨大片久久 | 99久久亚洲综合精品成人| 久久九九有精品国产23百花影院| 久久精品桃花综合| 久久精品无码专区免费东京热| 国产人久久人人人人爽| 久久精品www| 无码AV中文字幕久久专区 | 亚洲精品无码专区久久同性男| 国产无套内射久久久国产| 国内精品久久久久久久久电影网| 久久成人影院精品777| 久久精品国产亚洲精品| 一个色综合久久| 国产精品久久久久无码av| 久久se这里只有精品|