zcmimi's blog
avatar
zc
2020-05-29 17:09:00
  • 本文总阅读量
查看原题

点击跳转

矩阵乘法

这题倍增加速比快速幂快,可以节省很多多余的计算

二进制拆位后才能矩阵运算

#include<bits/stdc++.h>
#define fur(i,x,y) for(int i=x;i<=y;++i)
typedef unsigned int ll;
ll rd(){ll x=0;char c;for(c=getchar();c<'0'||'9'<c;c=getchar());for(x=c-48,c=getchar();'0'<=c&&c<='9';x=x*10+c-48,c=getchar());return x;}
char cr[50];int tt;
void print(ll x){
    if(!x)putchar('0');
    while(x)cr[++tt]=x%10+'0',x/=10;
    while(tt)putchar(cr[tt--]);
    putchar('\n');
}
int n,m,q;ll f[101],g[101],t[101];
struct mat{bool a[101][101];}bs[32];
mat operator*(mat a,mat b){
    mat c;
    fur(i,1,n)fur(j,1,n){
        c.a[i][j]=0;
        fur(k,1,n)c.a[i][j]^=a.a[i][k]&b.a[k][j];
    }
    return c;
}
void mul(mat x){
    memset(t,0,n*4+4);
    fur(i,1,n)fur(j,1,n)
        if(x.a[i][j])t[i]^=g[j];
    fur(i,1,n)g[i]=t[i];
}
ll solve(ll v){
    fur(i,1,n)g[i]=f[i];
    fur(i,0,31)if((v>>i)&1)mul(bs[i]);
    return g[1];
}
int main(){
    n=rd(),m=rd(),q=rd();
    int x,y;;
    fur(i,1,n)f[i]=rd();
    fur(i,1,m)
        x=rd(),y=rd(),
        bs[0].a[x][y]=bs[0].a[y][x]=1;
    fur(i,1,31)bs[i]=bs[i-1]*bs[i-1];
    while(q--)print(solve(rd()));
}
LG 6569 [NOI Online 3 提高组]魔法值
comment评论
Search
search