题目描述

小辉得到了一个包含 n 个数的数列，他要从中选出两个不同位置的数形成个一个数对，要求较左边的数对 k 取余的结果小于等于较右边的数对 k 取余的结果。

问小辉有多少种选法。

输入格式

第一行，两个正整数 n 和 k

接着 n 个正整数，为数列的值。

数据范围

50% 的数据，2 <= n <= 10000 , 1 <= k <= 10 数列中每个数的值不超过 1000

100% 的数据，2 <= n <= 1000000, 1 <= k <= 50 ，数列中每个数的值不超过 1000

输出格式

一个正整数，表示答案。

样例

4 6
3 4 5 6

3

样例解释

3 , 4 , 5 , 6 对 6 取模的结果分别为 3 , 4 , 5 , 0 能构成的数对有 (3,4)、(3,5)、(4,5)，共 3 个

解题思路

按照套路转换问题： 第 i 个数字和前面的某个数组配对（按照题目条件），看最终能配对成功多少对数字。

如果第 i 个数模 k 得到 10，那么就可以和 i 前面模 k 等于 0~10 的数字配对。进一步推广，如果第 i 个数模 k 为 j ，那么就可以和前面 1 到 i-1 位置模 k 为 0~j 的数字配对。

完善程序

#include<bits/stdc++.h>
using namespace std;
int sum[50];
long long ans;
int main()
{
	int n,k,t;
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&t);
		t = 填空(1);

		for(int j=0;填空(2);j++)
			ans += 填空(3);
		
		sum[t] = 填空(4);
	}

	printf("%lld",ans);
	return 0;
}

填空(1):{{ input(1) }}

填空(2):{{ input(2) }}

填空(3):{{ input(3) }}

填空(4):{{ input(4) }}

填空(5)：按照上面的算法，本题最坏的情况下计算复杂度为： O( {{ input(5) }} )