loj#P2463. 「2018 集训队互测 Day 1」完美的旅行
「2018 集训队互测 Day 1」完美的旅行
题目描述
小 A 有一张 个点的图,点的标号为 到 。点 到点 有 条有向边。可能有自环。
现在小 A 要在图上进行若干次旅行。每次旅行都是选任意一个起点,走至少一步,走到任意一个终点。定义一次旅行的愉悦值为起点与终点编号按位与的值。
好奇的小 B 想要知道:对于所有 和 ,小 A 进行了若干次旅行,总共走了 步,且所有旅行的愉悦值的按位与为 的方案数。
两种方案不同当且仅当旅行次数不同或某一次旅行不完全相同。
为了防止输出过多,你只需要输出这 个数对 取模后的结果的按位异或值。
为方便起见,保证 是 的幂次。
输入格式
第一行两个数 。
后面一个 的矩阵,第 行第 列的数表示点 到点 的有向边的数量。
输出格式
输出一个数表示 个答案取模后的异或值。
2 3
1 2
3 4
1770
数据范围与提示
对于所有数据,$2 \leq n \leq 64,1 \leq m \leq 20000,0 \leq A_{i,j} < 998244353$,保证 是 的幂。
子任务编号 | 分值 | 特殊限制 | ||
---|---|---|---|---|
,其中 表示按位异或运算 | ||||