1249 : 三数之和

时间限制Time Limit
1 秒Sec
内存限制Memory Limit
512 兆MB
提交次数Submitted
549 次Times
通过次数Solved
69 次Times

题目描述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