记录编号	566086	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI Online 2020 3rd]魔法值	最终得分	100
用户昵称	遥时_彼方	是否通过	通过
代码语言	C++	运行时间	0.316 s
提交时间	2021-11-01 13:30:33	内存使用	8.76 MiB

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
int nc,mc,qc;
ll ox=1;
ll q[101];
ll qmx;
struct jx
{
    ll p[101][101];
}ksm[64];
jx ft;
jx JXXC(jx a,int x1,int y1,jx b,int x2,int y2)
{
    jx c;
//    cout<<endl;
    for(int i1=1;i1<=x1;i1++)
    {
        for(int i2=1;i2<=y2;i2++)
        {
            c.p[i1][i2]=0;
            for(int i3=1;i3<=x2;i3++)
            {
                c.p[i1][i2]^=(a.p[i1][i3]*b.p[i3][i2]);
//                cout<<a.p[i1][i3]<<" "<<b.p[i3][i2]<<" "<<c.p[i1][i2]<<"\n";
            }
//            cout<<endl;
//            cout<<i1<<" "<<i2<<":"<<c.p[i1][i2]<<endl;
        }
//        cout<<endl;
    }
//    cout<<endl<<endl;;
//    for(int i=1;i<=x1;i++)
//    {
//        for(int o=1;o<=y2;o++)
//        {
//            cout<<c.p[i][o]<<" ";
//        }
//        cout<<endl;
//    }
    return c;
}
void YCL()
{
    int i=0;
    while(qmx) 
    {
        i++;
//        cout<<"ksm:"<<i<<endl;
        ksm[i]=JXXC(ksm[i-1],nc,nc,ksm[i-1],nc,nc);
        qmx>>=1;
    }
//    cout<<"i: "<<i<<endl;
    return;
}
void SC(ll x)
{
    jx s=ft;
    int i=0;
    while(x)
    {
        if(x&ox) s=JXXC(s,1,nc,ksm[i],nc,nc);
        x>>=1;
        i++;
    }
//    cout<<"i: "<<i<<endl;
    printf("%lld\n",s.p[1][1]);
    return;
}
int main()
{
    freopen("2020_magic.in","r",stdin);
	freopen("2020_magic.out","w",stdout);
	cin>>nc>>mc>>qc;
	for(int i=1;i<=nc;i++) scanf("%lld",&ft.p[1][i]);
	int s1,s2;
	for(int i=1;i<=mc;i++)
	{
	    scanf("%d%d",&s1,&s2);
	    ksm[0].p[s1][s2]=1;
        ksm[0].p[s2][s1]=1;
    }
    for(int i=1;i<=qc;i++)
    {
        scanf("%lld",&q[i]);
        qmx=max(q[i],qmx);
    }
    YCL();
    for(int i=1;i<=qc;i++)
    {
        SC(q[i]);
    }
    return 0;
}
//3 3 10
//0 0 1
//1 2
//1 3
//2 3
//1
//2
//3
//4
//5
//6
//7
//8
//9
//10
//0 1 1
//1 0 1
//1 1 0
//
//1 2:0
//
//0 1 0
//1 0 0
//1 1 1
//
//1 2:1