luogu#P7717. 「EZEC-10」序列

    ID: 11715 远端评测题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>动态规划dp2021O2优化深度优先搜索DFS数位 dp图的建立建图字典树Trie 树位运算按位

「EZEC-10」序列

题目背景

精准的解析刻画,是应该首先尝试的突破口。

——command_block 《考前小贴士》

题目描述

请问有多少个不同的序列 aa,满足:

  1. aa 的长度为 nn
  2. aa 中的元素均为不大于 kk 的非负整数。
  3. 满足 mm 组形如 (xi,yi,zi)(x_i,y_i,z_i)xi<yix_i<y_i 的限制,每组限制的意义为 axiayi=zia_{x_i} \oplus a_{y_i} = z_i\oplus 表示按位异或运算)。

两个序列相同,当且仅当它们所有元素均相同。

请输出答案对 109+710^9+7 取模的结果。

输入格式

输入共 m+1m+1 行:

  • 第一行三个数,n,m,kn,m,k
  • 接下来 mm 行,每行 33 个数,xi,yi,zix_i,y_i,z_i

输出格式

输出仅一行,表示答案对 109+710^9+7 取模的结果。

3 1 2
1 2 1
6
5 1 12
1 2 3

26364

提示

【样例 11 说明】

共有 66 种序列:$\{0,1,0\},\{0,1,1\},\{0,1,2\},\{1,0,0\},\{1,0,1\},\{1,0,2\}$。

【数据规模与约定】

本题采用捆绑测试。

  • Subtask 1(1 point):n=1n=1
  • Subtask 2(5 points):m=0m=0
  • Subtask 3(15 points):n,m,k5n,m,k\le 5
  • Subtask 4(10 points):zi=0z_i=0
  • Subtask 5(20 points):k16k\le 16
  • Subtask 6(2 points):数据随机。
  • Subtask 7(47 points):无特殊限制。

对于 100%100\% 的数据,1n5×1051 \leq n \leq 5 \times 10^50m5×1050 \le m \le 5 \times 10^50zi<2300 \le z_i<2^{30}1k<2301 \leq k< 2^{30}1xi,yin1\le x_i,y_i\le n

【提示】

如果你不知道什么是异或,请点击这里