1249 : 三数之和
- 时间限制Time Limit
- 1 秒Sec
- 内存限制Memory Limit
- 512 兆MB
- 提交次数Submitted
- 549 次Times
- 通过次数Solved
- 69 次Times
标准评测 Standard
从标准输入读入,结果写到标准输出。评测将输出拆成 token,与标准答案逐项比较,不按整段逐字节比对。
Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.
| 比对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
【题目背景】
小艾在计算理论课上了解到,三数之和(3SUM)问题在某种意义上是一个惊人困难的问题。当值域在 \(n^2\) 级别时,目前依然没有发现比朴素算法快很多的做法。
TA 想知道,如果值域大到一个惊人的程度时,你能够做到多好呢?
【题目描述】
给定 \(n\) 个整数 \(a_1,\dots,a_n\) 和一个模数 \(M\),保证 \(M = 10^K-1\),由输入一个正整数 \(K\) 的方式给出。
请你找出有多少对 \((i, j, k)\)(\(1\leq i\leq j\leq k\leq N\)),满足 \(a_i + a_j + a_k \equiv 0 \pmod M\)。
输入格式Input
第一行输入两个正整数 \(n,K\)(\(1\leq n\leq 500\),\(1\leq K\leq 2\times 10^4\))。
接下来 \(n\) 行每行输入一个整数,第 \(i\) 个数为 \(a_i\)。
保证输入的每个 \(a_i\) 非负,且不超过 \(2\times 10^4\) 位。
输出格式Output
一行输出一个数,表示满足要求的 \((i,j,k)\) 的方案数。
样例Sample
提示Hint
【样例解释 #0】
三组方案是:
- \(0 + 0 + 0 \equiv 0 \pmod 9\),
- \(0 + 1 + 17 \equiv 0 \pmod 9\),
- \(0 + 10 + 17 \equiv 0 \pmod 9\)。
出题Author
THU
题目到此结束End of problem