C - Assortment of Sweets Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君はお菓子屋さんで N 個のお菓子を見つけました。i 番目 (1 \leq i \leq N) のお菓子のカロリーは正整数 A_i です。

高橋君は、これらのお菓子の中から 1 個以上を選んで詰め合わせを作ろうとしています。高橋君はカロリー管理にこだわりがあり、選んだお菓子のカロリーの総和が K で割り切れるようにしたいと考えています。

条件を満たすお菓子の選び方の数を求めてください。すなわち、\{1, 2, \ldots, N\} の空でない部分集合 S であって、\displaystyle\sum_{i \in S} A_i が K で割り切れるものの個数を求めてください。

ただし、お菓子は番号で区別します。カロリーの値が同じお菓子が複数あっても、番号が異なれば異なる選び方として数えます。

答えは非常に大きくなる場合があるので、998244353 で割った余りを出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • N \times K \leq 2 \times 10^7
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数である。

入力

N K
A_1 A_2 \ldots A_N
  • 1 行目には、お菓子の個数を表す整数 N と、倍数の基準となる正整数 K が、スペース区切りで与えられる。
  • 2 行目には、各お菓子のカロリーを表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。

出力

選んだお菓子のカロリーの総和が K で割り切れるような、\{1, 2, \ldots, N\} の空でない部分集合の数を 998244353 で割った余りを 1 行で出力せよ。

入力例 1

4 3
1 2 3 4

出力例 1

5

入力例 2

2 5
1 2

出力例 2

0

入力例 3

12 10
7 13 20 4 16 9 25 30 11 6 18 2

出力例 3

411

入力例 4

50 60
1 999999937 120 45 78 300 17 2048 999999999 60 61 122 183 244 305 366 427 488 549 610 671 732 793 854 915 976 1037 1098 1159 1220 1281 1342 1403 1464 1525 1586 1647 1708 1769 1830 1891 1952 2013 2074 2135 2196 2257 2318 2379 1000000000

出力例 4

1108801

入力例 5

1 1
1000000000

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi found N sweets in a sweet shop. The calorie of the i-th sweet (1 \leq i \leq N) is a positive integer A_i.

Takahashi wants to make an assortment by choosing one or more of these sweets. He is very particular about calorie control and wants the sum of the calories of the chosen sweets to be divisible by K.

Find the number of ways to choose sweets that satisfy this condition. Specifically, find the number of non-empty subsets S of \{1, 2, \ldots, N\} such that \displaystyle\sum_{i \in S} A_i is divisible by K.

Note that the sweets are distinguished by their indices. Even if multiple sweets have the same calorie value, they are treated as distinct if their indices are different.

Since the answer can be very large, find the count modulo 998244353.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq 2 \times 10^5
  • N \times K \leq 2 \times 10^7
  • 1 \leq A_i \leq 10^9
  • All input values are integers.

Input

N K
A_1 A_2 \ldots A_N
  • The first line contains the integer N, representing the number of sweets, and the positive integer K, representing the divisor, separated by a space.
  • The second line contains the integers A_1, A_2, \ldots, A_N, representing the calories of each sweet, separated by spaces.

Output

Print the number of non-empty subsets of \{1, 2, \ldots, N\} such that the sum of the calories of the chosen sweets is divisible by K, modulo 998244353, in a single line.

Sample Input 1

4 3
1 2 3 4

Sample Output 1

5

Sample Input 2

2 5
1 2

Sample Output 2

0

Sample Input 3

12 10
7 13 20 4 16 9 25 30 11 6 18 2

Sample Output 3

411

Sample Input 4

50 60
1 999999937 120 45 78 300 17 2048 999999999 60 61 122 183 244 305 366 427 488 549 610 671 732 793 854 915 976 1037 1098 1159 1220 1281 1342 1403 1464 1525 1586 1647 1708 1769 1830 1891 1952 2013 2074 2135 2196 2257 2318 2379 1000000000

Sample Output 4

1108801

Sample Input 5

1 1
1000000000

Sample Output 5

1