POJ3150Cellular Automaton 矩阵快速幂+优化

http://vjudge.net/problem/POJ-3150
题解

比较好推出转移矩阵：
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
但是矩阵相乘500*500*500*log(k)还是会超时
可以观察这个转移矩阵，其实只知道第一行就可以推出每行，每列，所以保留第一行作为转移矩阵，这样就从N^3变成了N^2。

#include<stdio.h>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
ll n,m,d,k,mtr[505],res[505];
void mul(ll a[],ll b[])
{
    ll t[505];
    memset(t,0,sizeof(t));
    for(int i=0;i<n;i++)
      //  if(a[i])
        for(int k=n+i,j=0;j<n;k--,j++)
        {
           int z=k%n;
         //  cout<<z<<endl;
           t[i]=t[i]+a[j]*b[z];
           t[i]%=m;
        }
    for(int i=0;i<n;i++) a[i]=t[i];
}
int main() {
    while(cin>>n>>m>>d>>k)
    {
        memset(mtr,0,sizeof(mtr));
        for(int i=0;i<n;i++) scanf("%d",&res[i]);
        for(int i=0;i<=d;i++) mtr[i]=1;
        for(int i=n-1;i>=n-d;i--) mtr[i]=1;
         ll ans[505];
        memset(ans,0,sizeof(ans));
        ans[0]=1;
        while(k)
        {
            if(k&1) mul(ans,mtr);
            k>>=1;
            mul(mtr,mtr);
        }
        mul(res,ans);
        for(int i=0;i<n;i++)
            printf(i==n-1?"%dn":"%d ",res[i]);

    }
}

最后

以上就是奋斗蓝天为你收集整理的POJ3150Cellular Automaton 矩阵快速幂+优化的全部内容，希望文章能够帮你解决POJ3150Cellular Automaton 矩阵快速幂+优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。