POJ 3150 Cellular Automaton

给你一个“轮”，在每一次运作中，对于每一个a[i]，更新a[i]= sum( a[j] ) % m，其中（min ( |i-j| ,n-|i-j| )<=d），
问，运行了K次以后轮中的数字是多少。
明显矩阵乘法的题，构造矩阵b[i][j]=1 if(（min ( |i-j| ,n-|i-j| )<=d）)，else b[i][j]=0
其实大致可以猜出来b矩阵是有规律的，用log(k)*n^3方法求出来输出一看，是个循环矩阵，
那么就可以用第一行更新下面每一行，而第一行是n^2求出来的。
所以矩阵乘法时间复杂度变成了n^2，于是不TLE了。。。
 
代码写的很易做图，主要是练一下类的重载运算符，明白了const到底是干吗用的：
[cpp]  
bool operator <(const point b)const{  
    return a.x
}  
第一个const 保证b不被改变，第二个const 保证原变量不被改变。
写这些大致想保证该不被改变的就不被改变吧（否则出现编译错误）。。
[cpp]  
#include  

#define X 510  
int min(int a,int b){  
    return a
}  
int abs(int x){  
    return x<0?-x:x;  
}  
int t[X],m;  
struct matrix{  
    int a[X][X],n;  
    void operator *(matrix b){  
        long long c;  
        int i,j,k;  
        for(i=0;i
            c=0;  
            for(k=0;k
                c=(c+(long long)a[0][k]*b.a[i][k])%m;  
            t[i]=c;  
        }  
        for(i=0;i
        for(i=1;i
            for(j=1;j
                a[i][j]=a[i-1][j-1];  
            a[i][0]=a[i-1][n-1];  
        }  
    }  
    void print(){  
        int i,j;  
        for(i=0;i
            for(j=0;j
                printf("%d ",a[i][j]);  
        puts("");  
    }  
}as,tmp;  
int main(){  
    int i,j,k,d,n;  
    while(~scanf("%d%d%d%d",&n,&m,&d,&k)){  
        for(i=0;i
            for(j=0;j
                as.a[i][j]=0;  
                if(min(abs(i-j),n-abs(i-j))<=d)  
                     tmp.a[j][i]=1;  
                else tmp.a[j][i]=0;  
            }  
        for(i=0;i
        as.n=n;tmp.n=n;  
//      tmp.print();  
        while(k){  
            if(k&1)as*tmp;  
            k>>=1; tmp*tmp;  
//          tmp.print();  
        }  
        for(i=0;i
            printf("%d%c",as.a[0][i],i==n-1?'\n':' ');  
    }  
    return 0;  
}

补充：软件开发 , C++ ,