#1758. 完美的旅行

    ID: 1758 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest125来源:qoj.ac数据:公开样例动态规划

完美的旅行

完美的旅行

题目描述

标题: 完美的旅行 - Problem - QOJ.ac

#4782. 完美的旅行

Statistics

The problem was used in the following contests:

小 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 的幂次。

输入格式

第一行两个数 n,m。

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

输出格式

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

样例数据

样例输入

2 3
1 2
3 4

样例输出

1770

样例解释

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

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

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

异或值为 1770。

子任务

对于所有数据,2≤n≤64,1≤m≤20000,0≤Ai,j<998244353,保证 n 是 2 的幂。

子任务编号 分值 n≤ m≤ 特殊限制 1 15 16 2000 无 2 15 32 10000 3 35 64 20000 Ai,j=i⊗j,其中 ⊗ 表示按位异或运算 4 35 无

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2 3
1 2
3 4
1770