叶落归根(hometown)

叶落归根(hometown)

题目描述

 

叶落归根——树叶从树根生发出来,凋落后最终还是回到树根。比喻事物总有一定的归宿。接下来是题目。

给定一个n个点的有向图G(点的编号为1~n),一开始落叶(仅作为一个代号,你也可以当成是Alice、Bob、甲乙丙丁戊己庚辛壬癸…)会在G的某个点s上。总共有t个单位时间,每个单位时间落叶都必须通过一条当前所在点的出边到达下一个点(有时下一个点和当前点会是相同的)。

需要注意的是,如果当前所在点没有任何出边,落叶就会在这个单位时间*离开这张图,并且我们认为落叶永远不会再回来了。

你要做的是对于每一个起始点s以及每一个总时长t(1<=t<=Q且为整数)求出落叶在起始点为s且经过t单位时间后的位置也是s的方案数。

两个方案不同,当且仅当两个方案中存在至少一个时刻落叶所经过的边不是图G中的同一条边。

为了便于检验,只需要输出所有情况(即所有不同的起始点和总时长,一共n*Q种情况)的方案数对给定正整数P取模后的异或和即可——也就是说,假设所有情况的方案数分别是ans1、ans2、ans3……你要输出的就是(ans1 mod P) xor (ans2 mod P) xor (ans3 mod P)……

 

输入

 

第一行3个整数n、Q、P,分别表示图G的点数、总时长t的上限和给定的模数P

接下来n行,每行n个整数,其中第i行第j个数表示图G中从i出发到j的单向边数目

 

输出

 

一行一个整数,表示所有情况的方案数对给定正整数P取模后的异或和

 

样例输入

2 2 1000000207
2 3
4 5

样例输出

50

提示

 

数据规模和约定

对于前10%的数据:n=2,Q=20

对于另外10%的数据:n=3,Q=12

对于前50%的数据:n<=20

对于100%的数据:1<=n<=100,P<=2^30,Q<=10000,对于任意一对(u,v),图G中从u到v的边数不超过2^30

 

来源


solution

就是一个矩阵,问你1-Q次方的对角线的和。

考虑枚举t(1<=t<=Q)

n^3乘出显然不行了。

那么可以分块。考虑令o=sqrt(n)

预处理矩阵的1~o次方 和x*o 次方(1<=x<=o)

那么每次相当于求对角线。n^2乘起来就行。

叶落归根(hometown)
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define maxn 10005
using namespace std;
int n,q,mod,o;
ll ans,A[320][102][102],B[320][102][102];
ll read(){
    int v=0;char ch;
    while(!isdigit(ch=getchar()));v=(v<<1)+(v<<3)+ch-48;
    while(isdigit(ch=getchar()))v=(v<<1)+(v<<3)+ch-48;
    return v;
}
int main(){
    cin>>n>>q>>mod;o=sqrt(q);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)A[1][i][j]=read();
    for(int x=2;x<=o;x++){
        for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
        for(int j=1;j<=n;j++){
            A[x][i][j]=(A[x][i][j]+A[x-1][i][k]*A[1][k][j])%mod;
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            B[1][i][j]=A[o][i][j];
    }
    int T=q/o+1;
    for(int x=2;x<=T;x++){
        for(int i=1;i<=n;i++)
        for(int k=1;k<=n;k++)
        for(int j=1;j<=n;j++){
            B[x][i][j]=(B[x][i][j]+B[x-1][i][k]*B[1][k][j])%mod;
        }
    }
    for(int i=1;i<=n;i++)A[0][i][i]=B[0][i][i]=1;
    for(int x=1;x<=q;x++){
        int t1=x/o,t2=x%o;
        for(int i=1;i<=n;i++){
            ll tmp=0;
            for(int k=1;k<=n;k++){
                tmp=(tmp+A[t2][i][k]*B[t1][k][i])%mod;
            }
            ans=ans^tmp;
        }
    }
    cout<<ans<<endl;
    return 0;
}
View Code

 

 

 

 

上一篇:102-构造函数的原理以及使用方法-【视频讲解】


下一篇:102. 二叉树的层次遍历