F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 5376. -- [2018国家集训队互测]完美的旅行

5376: [2018国家集训队互测]完美的旅行

Time Limit: 80 Sec  Memory Limit: 512 MB
Submit: 16  Solved: 4
[Submit][Status][Discuss]

Description

小A有一张n个点的图,点的标号为0到n-1。点i到点j有Ai,j条有向边。可能有自环。现在小A要在图上进行若干次
旅行。每次旅行都是选任意一个起点,走至少一步,走到任意一个终点。定义一次旅行的愉悦值为起点与终点编号
按位与的值。好奇的小B想要知道:对于所有x∈[1,m]和y∈[0,n),小A进行了若干次旅行,总共走了x步,且所有
旅行的愉悦值的按位与为y的方案数。两种方案不同当且仅当旅行次数不同或某一次旅行不完全相同。为了防止输
出过多,你只需要输出这n×m个数对998244353取模后的结果的按位异或值。为方便起见,保证n是2的幂次。

Input

第一行两个数n,m。
后面一个n×n的矩阵,第i行第j列的数表示点i-1到点j-1的有向边的数量。
对于所有数据,2≤n≤64,1≤m≤20000,0≤Ai,j<998244353,保证n是2的幂。

Output

输出一个数表示n×m个答案取模后的异或值。

Sample Input

2 3
1 2
3 4

Sample Output

1770
样例解释
走 1 步,愉悦值的按位与 =0,1 的方案数分别为 6,4。
走 2 步的方案数分别为 116,38。
走 3 步的方案数分别为 2012,358。
异或值为 1770。

HINT

Source

day1

[Submit][Status][Discuss]

HOME Back