QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

# 4782. 完美的旅行

统计

小 A 有一张 $n$ 个点的图,点的标号为 $0$ 到 $n-1$。点 $i$ 到点 $j$ 有 $A_{i,j}$ 条有向边。可能有自环。

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

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

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

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

为方便起见,保证 $n$ 是 $2$ 的幂次。

输入格式

第一行两个数 $n,m$。

后面一个 $n\times n$ 的矩阵,第 $i$ 行第 $j$ 列的数表示点 $i-1$ 到点 $j-1$ 的有向边的数量。

输出格式

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

样例数据

样例输入

2 3
1 2
3 4

样例输出

1770

样例解释

走 $1$ 步,愉悦值的按位与 $=0,1$ 的方案数分别为 $6,4$。

走 $2$ 步的方案数分别为 $116,38$。

走 $3$ 步的方案数分别为 $2012,358$。

异或值为 $1770$。

子任务

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

子任务编号 分值 $n \leq$ $m \leq$ 特殊限制
$1$ $15$ $16$ $2000$
$2$ $15$ $32$ $10000$
$3$ $35$ $64$ $20000$ $A_{i,j}=i\otimes j$,其中 $\otimes$ 表示按位异或运算
$4$ $35$