loj#P2463. 「2018 集训队互测 Day 1」完美的旅行

    ID: 15733 传统题 3000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数学矩阵多项式 / 形式幂级数图论生成函数 / 母函数Berlekamp-Massey 算法2018集训队互测

「2018 集训队互测 Day 1」完美的旅行

题目描述

小 A 有一张 nn 个点的图,点的标号为 00n1n-1。点 ii 到点 jjAi,jA_{i,j} 条有向边。可能有自环。

现在小 A 要在图上进行若干次旅行。每次旅行都是选任意一个起点,走至少一步,走到任意一个终点。定义一次旅行的愉悦值为起点与终点编号按位与的值。

好奇的小 B 想要知道:对于所有 x[1,m]x \in [1,m]y[0,n)y \in [0,n),小 A 进行了若干次旅行,总共走了 xx 步,且所有旅行的愉悦值的按位与为 yy 的方案数。

两种方案不同当且仅当旅行次数不同或某一次旅行不完全相同。

为了防止输出过多,你只需要输出这 n×mn\times m 个数对 998244353998244353 取模后的结果的按位异或值。

为方便起见,保证 nn22 的幂次。

输入格式

第一行两个数 n,mn,m

后面一个 n×nn\times n 的矩阵,第 ii 行第 jj 列的数表示点 i1i-1 到点 j1j-1 的有向边的数量。

输出格式

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

2 3
1 2
3 4
1770

数据范围与提示

对于所有数据,$2 \leq n \leq 64,1 \leq m \leq 20000,0 \leq A_{i,j} < 998244353$,保证 nn22 的幂。

子任务编号 分值 nn \leq mm \leq 特殊限制
11 1515 1616 20002000
22 1515 3232 1000010000
33 3535 6464 2000020000 Ai,j=ijA_{i,j}=i\otimes j,其中 \otimes 表示按位异或运算
44 3535