学步园

这货就是个坑啊，80^5次方都可以过，数据太水了把。。。

快速矩阵比较：

就是把一个矩阵乘上一个{1,2,3，。。。。m}的向量，得到的矩阵叫做比较阵

这样能顺利把比较的复杂度降到o（n），不过需要注意的两个比较阵相同，不一定意味着两个原来的矩阵一定相同

这个就和hash一样，是有碰撞的，这个原理也就是hash，要是没有碰撞的话，得用80进制，太大了，存不下。

就是这个hash碰撞概率比较小而已，要找到碰撞的话还是很容易的

http://acm.hdu.edu.cn/showproblem.php?pid=2807

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int MAXN=80+10;
int n,m;
struct Matrix
{
    int v[MAXN][MAXN],c[MAXN];
    void cal()
    {
        memset(c,0,sizeof(c));
        for(int j=0; j<m; j++)
            for(int i=0; i<m; i++)
            {
                c[i]+=v[i][j]*(i+1);
            }
    }
    void init()
    {
        memset(v,0,sizeof(v));
    }
    void readin()
    {
        for(int i=0; i<m; i++)
            for(int j =0; j<m; j++)
                scanf("%d",&v[i][j]);
        cal();
    }
    bool operator ==(const Matrix &a) const
    {
        for(int i=0; i<m; i++)
                if(c[i]!=a.c[i])
                    return false;
        return true;
    }
    Matrix operator *(const Matrix &a) const
    {
        Matrix ans;
        ans.init();
        for(int i=0; i<m; i++)
            for(int k=0; k<m; k++)
                if(v[i][k])
                    for(int j=0; j<m; j++)
                        ans.v[i][j]+=v[i][k]*a.v[k][j];
        ans.cal();
        return ans;
    }
};
int G[MAXN][MAXN];
Matrix a[MAXN];
int main()
{
//    freopen("in","r",stdin);
    int INF;
//    cout<<pow(80,80)<<endl;
    while(~scanf("%d%d",&n,&m))
    {
        if(n==0 && m==0 )break;
        memset(G,0x3f,sizeof(G));
        INF=G[0][0];
        for(int i=0; i<n; i++)
            a[i].readin();
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<n; j++)
            {
                if(i==j) continue;
                Matrix ret=a[i]*a[j];
                for(int k=0; k<n; k++)
                {
                    if(k==i || k==j) continue;
                    if(ret==a[k])
                        G[i][k]=1;
                }
            }
        }
        for(int i=0; i<n; i++) G[i][i]=0;
        for(int k=0; k<n; k++)
            for(int i=0; i<n; i++)
                for(int j=0; j<n; j++)
                    G[i][j]=min(G[i][j],G[i][k]+G[k][j]);

        int q;
        scanf("%d",&q);
        while(q--)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            u--,v--;
            int ans=G[u][v];
            if(ans>=INF)
                puts("Sorry");
            else
                printf("%d\n",ans);
        }
    }
    return 0;
}