• <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>

            poj3233

            Matrix Power Series

            Time Limit: 3000MS
            Memory Limit: 131072K
            Total Submissions: 10211
            Accepted: 4333

            Description

            Given a n × n matrix A and a positive integer k, find the sum S = A + A2 + A3 + … + Ak.

            Input

            The input contains exactly one test case. The first line of input contains three positive integers n (n ≤ 30), k (k ≤ 109) and m (m < 104). Then follow n lines each containing n nonnegative integers below 32,768, giving A’s elements in row-major order.

            Output

            Output the elements of S modulo m in the same way as A is given.

            Sample Input

            2 2 4
            0 1
            1 1

            Sample Output

            1 2
            2 3
             
            題意很簡單不用描述了
            網上在推薦這題的時候可能有些誤區
            網上說是二分再二分,
            其實是這樣的,因為計算a^k可以二分,這是第二個二分
            而第一個二分是指的對a^1+a^2+....+a^k可以分成兩半  
            k是偶數時候
            f[k]=(a^1+a^2+....+a^(k/2))+a^(k/2)*[a^1+a^2+....+a^(k/2)]
            即 f[k]=f[k/2]+[a^(k/2)]*f[k/2]
            奇數時候 
            f[k]=f[k-1]+a^k
            以上描述的兩次二分是第一種做法
            第二種做法
            運用線性代數的
            令B= A E
                 0 E
            那么
            B^(k+1)= A^(k+1)  E+A+...A^k
                     0        E
             
            然后就不用多說了
             
            剛開始想出第一種方法,覺著也不難寫 ,
            然后wa到死 tle到死
            一直超時,那個取模那個如果不取就wa,取了就tle,真心糾結了
            然后忍不了了
            寫的第二個
            不知道為什么還是那么長時間
            應該是我寫的代碼質量不好
            #include<stdio.h>
            #include
            <string.h>
            #include
            <math.h>
            #include
            <iostream>
            #define maxn 35*2
            using namespace std;
            struct node
            {
                __int64 x[maxn][maxn];
                
            void init()
                
            {
                    memset(x,
            0,sizeof(x));
                }

                
            void init1()
                
            {
                    memset(x,
            0,sizeof(x));
                    
            for(int i=1; i<maxn; i++)
                        x[i][i]
            =1;
                }

            }
            ;
            node e;
            int m,n,k;
            void print1(node x)
            {
                
            for(int i=1; i<=n; i++)
                
            {
                    
            for(int j=1+n; j<=2*n; j++)
                    
            {
                        printf(
            "%d",x.x[i][j]);
                        
            if(j==n*2) printf("\n");
                        
            else printf(" ");
                    }

                }

            }

            node add1(node x)
            {
                node tmp;
                tmp
            =x;
                
            for(int i=1;i<=n;i++)
                
            {
                    
            for(int j=n+1;j<=2*n;j++)
                        tmp.x[i][j]
            =(tmp.x[i][j]%m+m)%m;
                }

                
            for(int i=1; i<=n; i++
                tmp.x[i][i
            +n]=(tmp.x[i][i+n]-1+m)%m;
                
            return tmp;
            }

            node mul(node t1,node t2)
            {
                node tmp;
                tmp.init();
                
            for(int i=1; i<=2*n; i++)
                    
            for(int j=1; j<=2*n; j++)
                    
            {
                        tmp.x[i][j]
            =0;
                        
            for(int k=1; k<=2*n; k++)
                        
            {
                            tmp.x[i][j]
            =(tmp.x[i][j]+t1.x[i][k]*t2.x[k][j])%m;
                        }

                    }

                
            return tmp;
            }

            node ap(node a,
            int p)
            {
                
            int tmp;
                node x,ans;
                tmp
            =p;
                ans.init1();
                x
            =a;
                
            while(tmp)
                
            {
                    
            if(tmp%2==1) ans=mul(ans,x);
                    tmp
            =tmp/2;
                    x
            =mul(x,x);
                }

                
            return ans;
            }

            int main()
            {
                node a,ans,b;
                scanf(
            "%d%d%d",&n,&k,&m);
                a.init();
                
            for(int i=1; i<=n; i++)
                    
            for(int j=1; j<=n; j++)
                    
            {
                        scanf(
            "%d",&a.x[i][j]);
                        a.x[i][j]
            =a.x[i][j]%m;
                    }

                b
            =a;
                
            for(int j=1; j<=n; j++)
                
            {
                    b.x[j][j
            +n]=1;
                    b.x[j
            +n][j+n]=1;
                }

                ans
            =ap(b,k+1);
                ans
            =add1(ans);
                print1(ans);
                
            return 0;
            }



            那個第一種方法tle,待會去優化下代碼,應該能過



            呼,第一種方法終于過了

            #include<stdio.h>
            #include
            <string.h>
            #include
            <math.h>
            #include
            <iostream>
            #define maxn 35
            #define inf 0x7fffffff
            using namespace std;
            struct node
            {
                __int64 x[maxn][maxn];
                
            void init()
                {
                    memset(x,
            0,sizeof(x));
                }
                
            void init1()
                {
                    memset(x,
            0,sizeof(x));
                    
            for(int i=1; i<maxn; i++)
                        x[i][i]
            =1;
                }
            };
            node e;
            int m,n,k;
            void print(node x)
            {
                
            for(int i=1; i<=n; i++)
                {
                    
            for(int j=1; j<=n; j++)
                    {
                        printf(
            "%d",x.x[i][j]);
                        
            if(j==n) printf("\n");
                        
            else printf(" ");
                    }
                }
            }
            node add(node t1,node t2)
            {
                node tmp;
                
            for(int i=1; i<=n; i++)
                    
            for(int j=1; j<=n; j++)
                    {
                        tmp.x[i][j]
            =(t1.x[i][j]+t2.x[i][j])%m;
                    }
                
            return tmp;
            }
            node mul(node t1,node t2)
            {
                node tmp;
                tmp.init();
                
            for(int i=1; i<=n; i++)
                    
            for(int j=1; j<=n; j++)
                    {
                        tmp.x[i][j]
            =0;
                        
            for(int k=1; k<=n; k++)
                        {
                            tmp.x[i][j]
            =(tmp.x[i][j]+t1.x[i][k]*t2.x[k][j]);
                            
            if(tmp.x[i][j]>=inf)
                            {
                                tmp.x[i][j]
            =tmp.x[i][j]%m;
                            }
                        }
                        tmp.x[i][j]
            =(tmp.x[i][j])%m;
                    }
                
            return tmp;
            }
            node ap(node a,
            int p)
            {
                
            int tmp;
                node x,ans;
                tmp
            =p;
                ans.init1();
                x
            =a;
                
            while(tmp)
                {
                    
            if(tmp%2==1) ans=mul(x,ans);
                    tmp
            =tmp/2;
                    x
            =mul(x,x);
                }
                
            return ans;
            }
            node getsum(node x,
            int n)
            {
                
            int k;
                node ans,tmp;
                k
            =n;
                
            if(k==1return x;
                
            if (k%2==0)
                {
                    tmp
            =getsum(x,k/2);
                    ans
            =add(tmp,mul(ap(x,k/2),tmp));
                }
                
            else
                {
                    tmp
            =getsum(x,k/2);
                    ans
            =add(add(tmp,mul(ap(x,k/2),tmp)),ap(x,k));
                }
                
            return ans;
            }
            int main()
            {
                node a,ans,b;
                scanf(
            "%d%d%d",&n,&k,&m);
                a.init();
                
            for(int i=1; i<=n; i++)
                    
            for(int j=1; j<=n; j++)
                    {
                        scanf(
            "%d",&a.x[i][j]);
                        a.x[i][j]
            =a.x[i][j]%m;
                    }
                ans
            =getsum(a,k);
                print(ans);
                
            return 0;
            }



            posted on 2012-07-22 07:02 jh818012 閱讀(106) 評論(0)  編輯 收藏 引用

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統計

            常用鏈接

            留言簿

            文章檔案(85)

            搜索

            最新評論

            • 1.?re: poj1426
            • 我嚓,,輝哥,,居然搜到你的題解了
            • --season
            • 2.?re: poj3083
            • @王私江
              (8+i)&3 相當于是 取余3的意思 因為 3 的 二進制是 000011 和(8+i)
            • --游客
            • 3.?re: poj3414[未登錄]
            • @王私江
              0ms
            • --jh818012
            • 4.?re: poj3414
            • 200+行,跑了多少ms呢?我的130+行哦,你菜啦,哈哈。
            • --王私江
            • 5.?re: poj1426
            • 評論內容較長,點擊標題查看
            • --王私江
            91精品国产综合久久久久久| 99久久人妻无码精品系列| 99久久无色码中文字幕| 久久ZYZ资源站无码中文动漫| 久久综合久久综合久久| 欧美一级久久久久久久大片| 亚洲国产精品无码久久久秋霞2 | 久久se精品一区二区| 亚洲国产一成久久精品国产成人综合| 日韩精品久久久肉伦网站| 品成人欧美大片久久国产欧美...| 伊人久久大香线蕉成人| 99精品久久精品| 一级做a爰片久久毛片看看| 91久久精一区二区三区大全| 国产伊人久久| 国产综合免费精品久久久| 亚洲欧美成人综合久久久| 久久丝袜精品中文字幕| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 久久福利青草精品资源站| 色播久久人人爽人人爽人人片AV| 国产高潮国产高潮久久久91| 午夜精品久久久内射近拍高清| AAA级久久久精品无码片| 2021久久精品免费观看| 久久精品无码av| 亚洲v国产v天堂a无码久久| 久久国产乱子精品免费女| 久久久亚洲AV波多野结衣| 久久久国产打桩机| 少妇被又大又粗又爽毛片久久黑人 | 久久国产视频99电影| 久久久久久a亚洲欧洲aⅴ | 俺来也俺去啦久久综合网| 午夜精品久久久久久毛片| 久久精品国产亚洲AV蜜臀色欲| 久久久精品国产免大香伊| 国产aⅴ激情无码久久| 久久精品国产亚洲av高清漫画 | 久久免费美女视频|