[集训队互测 2018] 完美的旅行

Luogu

IDLGP9249

Time3000ms

Memory512MB

DifficultyP7

数学图论2018集训队互测多项式矩阵加速生成函数

小 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$ 的幂次。 ## Input 第一行两个数 $n,m$。后面一个 $n\times n$ 的矩阵，第 $i$ 行第 $j$ 列的数表示点 $i-1$ 到点 $j-1$ 的有向边的数量。 ## Output 输出一个数表示 $n\times m$ 个答案取模后的异或值。 [samples] ## Note ### 样例解释走 $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 $ | $64$ | $20000$ | |

Samples

Input #1

2 3
1 2
3 4

Output #1

API Response (JSON)

{
  "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 进行了...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments