设为首页 加入收藏

TOP

poj 3150 Cellular Automaton（矩阵快速幂）
2015-07-24 06:13:07 来源: 作者: 【大 中 小】 浏览:46次
Tags：poj 3150 Cellular Automaton 矩阵 快速

?

?

大致题意：给出n个数，问经过K次变换每个位置上的数变为多少。第i位置上的数经过一次变换定义为所有满足 min( abs(i-j),n-abs(i-j) )<=d的j位置上的数字之和对m求余。

?

思路：

我们先将上述定义表示为矩阵

B =

1 1 0 0 1
1 1 1 0 0
0 1 1 1 0
0 0 1 1 1
1 0 0 1 1

B[i][j] = 表示i与j满足上述关系，B[i][j] = 0表示i与j不满足上述关系。根据这个矩阵，那么样例1中1 2 2 1 2经过一次变换变成了5 5 5 5 4。

其实这也是矩阵相乘的问题，令A = 1 2 2 1 2，那么A * B = 5 5 5 5 4。那么要经过K次变换，答案无疑是 A*（B^k）mod m。

用矩阵快速幂的复杂度为 O(n^3 * log k),n最大是500，K也很大，必会TLE。logk是不会变了，优化在于n^3。仔细观察B矩阵，发现它是有规律的，它的每一行都是它上一行右移一位得到的。那么在矩阵相乘时，我们只需计算第一行，然后整个矩阵就算出来了，这样复杂度降为O(n^2 * log k)。

?

?

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include
       #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #define LL long long #define _LL __int64 #define eps 1e-8 #define PI acos(-1.0) using namespace std; const int INF = 0x3f3f3f3f; const int maxn = 510; int n,m,d,k; _LL c[maxn][maxn]; _LL a[maxn][maxn],b[maxn]; int main() { while(~scanf(%d %d %d %d,&n,&m,&d,&k)) { for(int i = 0; i < n; i++) scanf(%I64d,&b[i]); for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if( min(abs(i-j),n-(abs(i-j))) <= d) a[i][j] = 1; else a[i][j] = 0; } } while(k) { if(k&1) { for(int i = 0; i < n; i++) { c[0][i] = 0; for(int j = 0; j < n; j++) { c[0][i] += b[j]*a[j][i]; } } for(int i = 0; i < n; i++) b[i] = c[0][i]%m; } for(int i = 0; i < 1; i++) { for(int j = 0; j < n; j++) { c[i][j] = 0; for(int k = 0; k < n; k++) c[i][j] += a[i][k]*a[k][j]; } } for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(i == 0) a[i][j] = c[i][j]%m; else a[i][j] = a[i-1][(j-1+n)%n]; } } k >>= 1; } for(int i = 0; i < n-1; i++) printf(%I64d ,b[i]); printf(%I64d ,b[n-1]); } return 0; }


?
【大 中 小】【打印】 【繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部】
分享到: 
上一篇：Acdreamoj1115(数学思维题) 下一篇：C++之易混淆知识点五

评论

帐　　号: 密码: (新用户注册)
验 证 码:
表　　情:
内　　容: