UVA 11551(矩阵快速幂)-蒲公英云

UVA 11551(矩阵快速幂)

题目来源:点击打开链接

题目题意:题目给我们n个数和r次操作。接在输入n行，表示每次将第i个数变成它后面几个位置的和。重复r次。

题目分析:我们按照题目的输入构造01矩阵，0表示不加上这个数，1表示加上。然后矩阵快速幂加速。

代码如下:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
const int mod=1000;
struct matrix
{
    int f[55][55];
    matrix operator*(const struct matrix &a) const {
        matrix ans;
        for (int i=0;i<50;i++) {
            for (int j=0;j<50;j++) {
                ans.f[i][j]=0;
                for (int k=0;k<50;k++) {
                    ans.f[i][j]=(ans.f[i][j]+f[i][k]*a.f[k][j])%mod;
                }
            }
        }
        return ans;
    }
}a,b;
matrix fast_pow(matrix base,int k)
{
    matrix ans=base;
    while (k) {
        if (k&1)
            ans=ans*base;
        base=base*base;
        k>>=1;
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while (t--) {
        int n,r;
        scanf("%d%d",&n,&r);
        memset (a.f,0,sizeof (a.f));
        memset (b.f,0,sizeof (b.f));
        for (int i=0;i<n;i++) {
            scanf("%d",&a.f[0][i]);
        }
        for (int i=0;i<n;i++) {
            int num;
            scanf("%d",&num);
            for (int j=0;j<num;j++) {
                int pos;
                scanf("%d",&pos);
                b.f[pos][i]=1;
            }
        }
        if (r==0) {
            for (int i=0;i<n;i++) {
                if (i==n-1) printf("%d\n",a.f[0][i]);
                else printf("%d ",a.f[0][i]);
            }
        }
        else {
            r--;
            matrix ans=fast_pow(b,r);
            ans=a*ans;
            for (int i=0;i<n;i++) {
                if (i==n-1) printf("%d\n",ans.f[0][i]);
                else printf("%d ",ans.f[0][i]);
            }
        }
    }
    return 0;
}