{"problem":{"name":"[集训队互测 2018] 完美的旅行","description":{"content":"小 A 有一张 $n$ 个点的图，点的标号为 $0$ 到 $n-1$。点 $i$ 到点 $j$ 有 $A_{i,j}$ 条有向边。可能有自环。 现在小 A 要在图上进行若干次旅行。每次旅行都是选任意一个起点，走至少一步，走到任意一个终点。定义一次旅行的愉悦值为起点与终点编号按位与的值。 好奇的小 B 想要知道：对于所有 $x \\in [1,m]$ 和 $y \\in [0,n)$，小 A 进行了","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9249"},"statements":[{"statement_type":"Markdown","content":"小 A 有一张 $n$ 个点的图，点的标号为 $0$ 到 $n-1$。点 $i$ 到点 $j$ 有 $A_{i,j}$ 条有向边。可能有自环。\n\n现在小 A 要在图上进行若干次旅行。每次旅行都是选任意一个起点，走至少一步，走到任意一个终点。定义一次旅行的愉悦值为起点与终点编号按位与的值。\n\n好奇的小 B 想要知道：对于所有 $x \\in [1,m]$ 和 $y \\in [0,n)$，小 A 进行了若干次旅行，总共走了 $x$ 步，且所有旅行的愉悦值的按位与为 $y$ 的方案数。\n\n两种方案不同当且仅当旅行次数不同或某一次旅行不完全相同。\n\n为了防止输出过多，你只需要输出这 $n\\times m$ 个数对 $998244353$ 取模后的结果的按位异或值。\n\n为方便起见，保证 $n$ 是 $2$ 的幂次。\n\n## Input\n\n第一行两个数 $n,m$。\n\n后面一个 $n\\times n$ 的矩阵，第 $i$ 行第 $j$ 列的数表示点 $i-1$ 到点 $j-1$ 的有向边的数量。\n\n## Output\n\n输出一个数表示 $n\\times m$ 个答案取模后的异或值。\n\n[samples]\n\n## Note\n\n### 样例解释\n\n走 $1$ 步，愉悦值的按位与 $=0,1$ 的方案数分别为 $6,4$。\n\n走 $2$ 步的方案数分别为 $116,38$。\n\n走 $3$ 步的方案数分别为 $2012,358$。\n\n异或值为 $1770$。\n\n### 数据范围\n\n对于所有数据，$2 \\leq n \\leq 64$，$1 \\leq m \\leq 20000$，$0 \\leq A_{i,j} < 998244353$，保证 $n$ 是 $2$ 的幂。\n\n|子任务编号\t|\t分值\t\t|\t$n \\leq$\t|\t$m \\leq$\t|\t\t特殊限制\t\t\t\t\t\t\t\t\t|\n|:----------------:|:----------------:|:----------------:|:----------------:|:-------------------------------------------------------------------------:|\n|\t$1$\t\t|\t$15$\t|\t$16$\t|\t$2000$\t|\t\t\t\t\t\t\t\t\t\t\t\t|\n|\t$2$\t\t|\t$15 $\t|\t$32$\t|\t$10000$\t|\t\t\t\t\t\t\t\t\t\t\t\t|\n|\t$3$\t\t|\t$35$\t|\t$64$\t|\t$20000$\t|$A_{i,j}=i\\otimes j$，其中 $\\otimes$ 表示按位异或运算\t|\n|\t$4$\t\t|\t$35 $\t|\t$64$\t|\t$20000$\t|\t\t\t\t\t\t\t\t\t\t\t\t|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9249","tags":["数学","图论","2018","集训队互测","多项式","矩阵加速","生成函数"],"sample_group":[["2 3\n1 2\n3 4","1770"]],"created_at":"2026-03-03 11:09:25"}}