1071 : Distinct Substrings
- 时间限制Time Limit
- 5 秒Sec
- 内存限制Memory Limit
- 512 兆MB
- 提交次数Submitted
- 78 次Times
- 通过次数Solved
- 28 次Times
| 比对Compare | token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored. |
|---|---|
| 不同则错Differs | token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ. |
| 输入Input | 标准输入,格式见题面。Standard input; format as in the statement. |
| 输出Output | 标准输出。Standard output. |
| 时间与内存Time and memory | 记这一份程序的 CPU 时间和内存峰值。题目上的时间限制、内存限制就是这一份的上限。The record is this program’s CPU time and peak memory. The limits on the problem apply to this one run. |
题目描述Description
For a string \(s_1, s_2, \dots, s_n\), Bobo denotes the number of its distinct substrings as \(f(s_1, s_2, \dots, s_n)\). He also defines \(h(c) = f(s_1, s_2, \dots, s_n, c) - f(s_1, s_2, \dots, s_n)\) for character \(c\).
Given a string \(s_1, s_2, \dots, s_n\) and \(m\), find the value of \(\bigoplus_{c = 1}^{m}\left(h(c) \cdot 3^c \bmod (10^9+7)\right)\).
Note that \(\oplus\) denotes the bitwise exclusive-or (XOR).
输入格式Input
The input consists of several test cases and is terminated by end-of-file.
The first line of each test case contains two integers \(n\) and \(m\).
The second line contains \(n\) integers \(s_1, s_2, \dots, s_n\).
- \(1 \leq n, m \leq 10^6\)
- \(1 \leq s_i \leq m\)
- The sum of \(n\) does not exceed \(5 \times 10^6\).
- The sum of \(m\) does not exceed \(5 \times 10^6\).
输出格式Output
For each test case, print an integer which denotes the result.
样例Sample
提示Hint
For the second test case, \(h(1) = h(2) = 2, h(3) = 3\).
出题Author
ftiasch