分数: 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