#P11799. 【MX-X9-T3】『GROI-R3』Powerless

    ID: 13109 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>O2优化数位 DP字典树 Trie梦熊比赛

【MX-X9-T3】『GROI-R3』Powerless

题目背景

你能走到这里很了不起......

题目描述

白给了你一个长度为 nn 的整数序列 a1,,ana_1,\ldots, a_n 和一个整数 mm,她请你求出以下式子的值:

$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=0}^m \min(a_i \oplus k, a_j \oplus k) $$

其中,\oplus 表示二进制下按位异或。

由于答案可能很大,所以你仅需要输出答案对 998244353998244353 取模后的值。

输入格式

第一行,两个非负整数 n,mn, m

第二行,nn 个非负整数 a1,,ana_1, \ldots, a_n

输出格式

仅一行,一个整数,表示答案对 998244353998244353 取模后的值。

2 3
1 5

40

5 7
1 2 3 4 5

460

10 197
1 5 102 289 445 326 117 64 100 266

2788560

10 0
3701780 6015893 9822195 8016360 992671 8828219 5674666 4815987 1784800 995151

333221210

8 33554432
2117455 10849252 28912108 3049487 10134324 20812345 26061978 24220183

42695030

8 51937970
93102591 5826965 25429632 51808294 13143740 21293750 85706705 22127009

345700571

13 189320127
90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115 90228115

425145733

10 1000000000
530093637 530093637 530093637 540208320 451233002 540208320 540208320 895132935 619514612 895132935

644847220

提示

【样例解释 #1】

i=j=1i = j = 1 时,$\sum\limits_{k=0}^m \min(x_i \oplus k, x_j \oplus k) = (1 \oplus 0) + (1 \oplus 1) + (1 \oplus 2) + (1 \oplus 3) = 1 + 0 + 3 + 2 = 6$;

i=j=2i = j = 2 时,$\sum\limits_{k=0}^m \min(x_i \oplus k, x_j \oplus k) = (5 \oplus 0) + (5 \oplus 1) + (5 \oplus 2) + (5 \oplus 3) = 5 + 4 + 7 + 6 = 22$;

i=1,j=2i = 1, j = 2i=2,j=1i = 2, j = 1 时,$\sum\limits_{k=0}^m \min(x_i \oplus k, x_j \oplus k) = \min(1, 5) + \min(0, 4) + \min(3, 7) + \min(2, 6) = 6$。

因此,答案为 6+22+6×2=406 + 22 + 6 \times 2 = 40

【数据范围】

本题采用捆绑测试。

子任务编号 nn\le mm\le aia_i\le 特殊性质 分值
1 100100 11
2 2×1052\times 10^5 00 10910^9 88
3 30003000 10610^6 10610^6 2121
4 2×1052\times 10^5 10910^9 1616
5 10910^9 A 99
6 B 2424
7 2121
  • 特殊性质 A:保证 a1=a2==ana_1 = a_2 = \cdots = a_n
  • 特殊性质 B:保证存在非负整数 kk 使得 m=2k1m = 2^k - 1

对于 100%100\% 的数据,保证 1n2×1051 \leq n \leq 2\times 10^50m1090 \leq m \leq 10^90ai1090 \leq a_i \leq 10^9