← 返回题目列表

AtCoder · abc427_f

F. 不相邻

中文机器翻译题面 查看原题


分数: 525 点

问题陈述

给你一个长度-N 整数序列 A=(A _ 1,A _ 2,\ldots,A _ N).

有 2 ^ N (不一定连续)的子序列 A。 找出有多少个子序列 (A _ {i _ 1},A _ {i _ 2},\ldots,A _ {i _ k})\ (1\le i _ 1\lt i _ 2\lt\cdots\lt i _ k\le N) 同时满足以下两个条件:

  • 所选元素在 A。也就是说, 1+i _ j\ne i _ {j+1} 适用于所有人 1\le j\lt k.
  • 总和是以下的倍数 M。也就是说, \displaystyle\sum _ {j=1} ^ kA _ {i _ j}\equiv0\pmod M.

即使两个子序列作为整数序列相等,如果它们的取位置不同,它们也会被单独计数。

约束

  • 1\le N\le60
  • 1\le M\le10 ^ 9
  • 0\le A _ i\lt M
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N M
A _ 1 A _ 2 \ldots A _ N

输出

打印答案。


示例输入 1

7 6
3 1 4 1 5 3 2

示例输出 1

6

以下六个子序列满足条件:

  • ()=()
  • (A _ 1,A _ 3,A _ 5)=(3,4,5)
  • (A _ 1,A _ 4,A _ 7)=(3,1,2)
  • (A _ 1,A _ 6)=(3,3)
  • (A _ 2,A _ 5)=(1,5)
  • (A _ 3,A _ 7)=(4,2)

因此,打印 6.


示例输入 2

15 10
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5

示例输出 2

798

示例输入 3

20 998244353
778718481 719092922 676292280 713825156 0 434453766 620370916 67922064 0 577696866 21516423 955580612 955580612 0 332156721 0 0 0 632133714 500614291

示例输出 3

40