1 条题解

  • 0
    @ 2025-10-8 16:52:34
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    int n,m,K;
    struct node
    {
        int a[110][110];
        node(){memset(a,0,sizeof(a));}
    };
    node operator* (node A,node B)
    {
        node C;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    C.a[i][j]=C.a[i][j]+A.a[i][k]*B.a[k][j];
        return C;
    }
    node qpow(node A,int b)
    {
        node C;for(int i=1;i<=n;i++)C.a[i][i]=1;
        for(;b;b>>=1)
        {
            if(b&1)C=C*A; 
            A=A*A;
        }
        return C;
    }
    int main()
    {
        scanf("%d%d%d",&n,&m,&K);
        node f[11];
        for(int i=1;i<=m;i++)
            for(int j=1;j<=n;j++)
            {
                int x;scanf("%d",&x);
                f[i].a[x][j]=1;
            }
        node A,ff;
        for(int i=1;i<=n;i++)A.a[1][i]=i;
        for(int i=1;i<=n;i++)ff.a[i][i]=1;
    
        for(int i=1;i<=m;i++)ff=ff*f[i];
        A=A*qpow(ff,K/m);
        for(int i=1;i<=K%m;i++)A=A*f[i];
        
        //for(int i=1;i<=K;i++)A=A*f[(i-1)%m+1];
        for(int i=1;i<=n;i++)printf("%d ",A.a[1][i]);
        return 0;
    }
    
    • 1

    信息

    ID
    598
    时间
    1000ms
    内存
    128MiB
    难度
    4
    标签
    递交数
    41
    已通过
    19
    上传者