Skip to content

11264: 【原1264】particle

题目

题目描述

author: Tongliang Liao 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1264

Description

一束粒子流在一个环形加速器中逆时针匀速运行。加速器上有n个节点,按照逆时针方向分别标号为0..n-1。每个节点上有m个小孔,粒子束将随机经由其中一个通过节点。 已知:

  1. 粒子束从0号节点的0号小孔进入环形加速器,且到达下一个节点用时1ns;

  2. 粒子束只能经由小孔穿过节点,但在相邻节点之间的运行路线却是随机的。对于任意i,从i号节点的第j个小孔到(i+1) mod n号节点的第k个小孔有a[i][j][k]种不同的路径。

丧心病狂的科学家们想要知道在粒子束飞行了k ns之后一共可能经过多少种不同的路径。两条路径不同当且仅当它们在某一刻经过了不同的小孔,或者在相邻节点之间选择了不同的路径。

由于答案可能很大,所以只要输出可能的路径数 mod 18446744073709551616。

Input Format

第一行输入n,m,k。

接下来n*m行,m列。每m行为一组。第i(1<=i<=n)组表示矩阵a[i-1],含义如题目所述。

对于10%的数据,k<=10,m<=3;

对于30%的数据,n<=10,m<=3;

对于50%的数据,k<=100;

对于60%的数据,n<=64,k<=10000;

对于100%的数据,n,m<=64,k<2^64。

以上数据范围均为包含关系。

Useless hint: 请注意数据的大小,选择合适的数据类型。

Output Format

输出路径数 mod 18446744073709551616。

Sample Input

2 3 3
1 1 1
1 1 1
1 1 1
0 0 1
0 1 0
1 0 0

Sample Output

9

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!