解题思路

余数分组

1. 求余数：把每个价格取模 $m$，记余数为 $r=a_i\bmod m$。
2. 统计频次：用数组 cnt[r] 记录余数 $r$ 出现的次数，大小为 $m$。

配对规则

• 若两件商品余数分别为 $r$ 与 $m-r$（$1\le r\ < m$），则 $r+(m-r)\equiv 0 \pmod m$。

• 特殊余数：

  • $r=0$ ：只能与自身配对，组合数为 $\binom{cnt[0]}{2}$
  • 当 $m$ 为偶数且 $r=m/2$ 时，同上，组合数为 $\binom{cnt[m/2]}{2}$

• 其它余数 $1\le r<\frac{m}{2}$：可与 $m-r$ 配对，组合数为 cnt[r] * cnt[m-r]。

组合数公式

总体算法

1. 统计余数出现次数 O(n)
2. 遍历 r = 1 … ⌊(m-1)/2⌋ 计算配对数
3. 处理 r = 0 和 (m/2)（若 m 为偶数）
4. 全程对 MOD 取模

复杂度分析

• 时间：$O(n+m)$（统计 + 遍历余数）
• 空间：$O(m)$（存余数计数）

代码

Python

import sys

MOD = 998244353
n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))

cnt = [0] * m          # 统计每个余数出现次数
for v in a:
    cnt[v % m] += 1

ans = cnt[0] * (cnt[0] - 1) // 2          # r = 0
for r in range(1, (m + 1) // 2):          # 1 <= r < m/2
    ans += cnt[r] * cnt[m - r]
if m % 2 == 0:                            # r = m/2
    ans += cnt[m // 2] * (cnt[m // 2] - 1) // 2

print(ans % MOD)

Java

import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 998244353L;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        long[] cnt = new long[m];                // 余数计数
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            long v = Long.parseLong(st.nextToken());
            cnt[(int) (v % m)]++;
        }

        long ans = cnt[0] * (cnt[0] - 1) / 2;    // r = 0
        for (int r = 1; r < (m + 1) / 2; r++) {  // 1 <= r < m/2
            ans = (ans + cnt[r] * cnt[m - r]) % MOD;
        }
        if (m % 2 == 0) {                        // r = m/2
            long c = cnt[m / 2];
            ans = (ans + c * (c - 1) / 2) % MOD;
        }
        System.out.println(ans % MOD);
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 998244353LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<long long> cnt(m, 0);          // 余数计数
    for (int i = 0; i < n; ++i) {
        long long x; cin >> x;
        ++cnt[x % m];
    }

    long long ans = cnt[0] * (cnt[0] - 1) / 2;  // r = 0
    for (int r = 1; r < (m + 1) / 2; ++r) {     // 1 <= r < m/2
        ans += cnt[r] * cnt[m - r];
    }
    if (m % 2 == 0) {                           // r = m/2
        ans += cnt[m / 2] * (cnt[m / 2] - 1) / 2;
    }
    cout << ans % MOD << '\n';
    return 0;
}

题目内容

多多正在参加一个特殊的满减活动,有几个名不相同的商品，每个商品的价格是$a_i$。活动规则是——若挑选的两个商品的价格总和是$m$的倍数的话，可以免费带走这两个商品，由于多多最多只能带两个商品，请问多多有多少种组合方式免费带两个商品。

输入描述

第一行输入两个数字$n$和$m$。

接下来输入$n$个商品的价格$a_i$，$a_i$为整数。

$1≤n≤200000,1≤m < 200000,1 ≤ a_i ≤ 1000000000$

输出描述

输出一个数字，表示多多鸡能免费带走两个商品的方式数量。

最终结果对$998244353$取模

样例1

输入

2 4
1 3

输出

1 

说明

多多只有$1$种方式免费拿走两件商品。

第$1$件商品和第$2$件商品

样例2

输入

5 2
1 2 3 4 5

输出

4

说明

多多有$4$种方式带走两件商品

第$1$件商品和第$3$件商品

第$2$件商品和第$4$件商品

第$1$件商品和第$5$件商品

第$3$件商品和第$5$件商品