hdu4965矩阵快速幂-白红宇

hdu4965矩阵快速幂

阅读量：5132 次

发布时间：2019-06-13

本文共 1146 字，大约阅读时间需要 3 分钟。

这题不能直接按常规做啊，因为数组根本就开不下，转换思维A（B*A）^(n*n-1)B

这样的话数组B*A就是10*10了，然后快速幂就行了

刚开始数组都开小了，tle，还找了半天bug。。。还有就是定义三个struct真累。。。

#include#include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #define pi acos(-1)#define ll long long#define mod 1000000007#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;const double g=10.0,eps=1e-9;const int N=1000+5,maxn=1<<10+5,inf=0x3f3f3f3f;struct NodeA{ ll row,col; ll a[N][10];};struct NodeB{ ll row,col; ll a[10][N];};struct Node{ ll row,col; ll a[10][10];};Node mul(Node x,Node y){ Node ans; ans.row=x.row,ans.col=y.col; memset(ans.a,0,sizeof ans.a); for(ll i=0;i
                  
                   >=1; } return ans;}int main(){ ios::sync_with_stdio(false); cin.tie(0); // cout<
                   
                    <
                    
                     >n>>m,n&&m){ NodeA A; A.row=n,A.col=m; for(ll i=0;i
                     
                      >A.a[i][j]; NodeB B; B.row=m,B.col=n; for(ll i=0;i
                      
                       >B.a[i][j]; Node C; C.row=m,C.col=m; memset(C.a,0,sizeof C.a); for(ll i=0;i