LG5107【能量采集】

· · 题解

题解同步发在博客

矩阵快速幂。

真的可惜啊，比赛的时候必须要去晚自修，导致一堆分都没拿，难受得一批。

说说这道题，出题人的原意是k进制矩乘是吧。然后我就正常倍增矩乘过了此题，让我很是震惊。

我既没有循环展开，也没有什么矩乘的时候乘了一定次数再膜来减少膜的次数，就是最老实的矩乘，可能我代码天生自带小常数。不过一些小技巧还是要注意一下的，比如说能减法就做减法，不要取模，然后尽量减少矩乘时的循环次数，比如记录一个矩阵大小，其他好像就没有什么了。

正式题解在此 ，有正式题解那我不用讲了，直接上代码。

code:

//2018.12.17 by ljz
#include<bits/stdc++.h>
using namespace std;
#define res register int
#define LL long long
#define inf 0x3f3f3f3f
#define eps 1e-15
inline int read(){
    res s=0;
    bool w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return w?-s:s;
}
inline void _swap(res &x,res &y){
    x^=y^=x^=y;
}
inline int _abs(const res &x){
    return x>0?x:-x;
}
inline int _max(const res &x,const res &y){
    return x>y?x:y;
}
inline int _min(const res &x,const res &y){
    return x<y?x:y;
}
const int N=50+10;
const int kcz=998244353;
namespace MAIN{
    struct Matrix{
        int t[N][N],n,m;
        Matrix() {memset(t,0,sizeof(t));}
        inline void INIT(){
            for(res i=0;i<n;i++)t[i][i]=1;
        }
    };
    int n,m,q;
    int a[N];
    inline void add(res &x,const res &y){
        x+=y,x>=kcz?x-=kcz:1;
    }
    inline Matrix operator * (const Matrix &x,const Matrix &y){
        Matrix cnt;
        for(res i=0;i<x.n;i++)
            for(res j=0;j<y.m;j++)
                for(res k=0;k<x.m;k++)add(cnt.t[i][j],1LL*x.t[i][k]*y.t[k][j]%kcz);
        cnt.n=x.n,cnt.m=y.m;
        return cnt;
    }
    Matrix ret,ans[32];
    inline int qpow(res x,res y){
        res ret=1;
        while(y){
            if(y&1)ret=1LL*ret*x%kcz;
            x=1LL*x*x%kcz,y>>=1;
        }
        return ret;
    }
    inline void MAIN(){
        n=read(),m=read(),q=read();
        for(res i=0;i<n;i++)ret.t[i][0]=read();
        ret.n=ret.m=1;
        ans[0].n=ans[0].m=n;
        ans[0].INIT();
        for(res i=1;i<=m;i++){
            res u=read(),v=read();
            ans[0].t[v-1][u-1]++;
        }
        for(res i=0;i<n;i++){
            res pos=0;
            for(res j=0;j<n;j++)add(pos,ans[0].t[j][i]);
            pos=qpow(pos,kcz-2);
            for(res j=0;j<n;j++)ans[0].t[j][i]=1LL*ans[0].t[j][i]*pos%kcz;
        }
        for(res i=1;i<=31;i++)ans[i]=ans[i-1]*ans[i-1];
        while(q--){
            res t=read();
            Matrix tmp=ret;
            for(res i=0;i<=31;i++)if((1<<i)&t)tmp=ans[i]*tmp;
            LL qaq=0;
            for(res i=0;i<n;i++)qaq^=tmp.t[i][0];
            printf("%lld\n",qaq%kcz);
        }
    }
}
int main(){
    MAIN::MAIN();
    return 0;
}