Logo Infinity Online Judge

InfOJ

时间限制:1 s 空间限制:512 MB

#30. 子集积

Statistics

题目描述

给出 $n$ 个整数 $a_1\sim a_n$,它们构成的多重集中,有几个子集的元素积大于 $m$?(空集的元素积等于 $1$)

两个子集不同,当且仅当它们中包含元素的 下标 不同。

答案很大,因此请输出它对 $998244353$ 取模的值。

输入格式

第一行两个整数 $n,m$。

接下来一行 $n$ 个正整数 $a_1\sim a_n$,描述这个多重集。

输出格式

一行一个整数,为答案对 $998244353$ 取模的值。

样例

输入 1

4 4
1 1 2 3

输出 1

4

输入 2

20 123456
1 5 12 24 189893 233333 2 22 134 3284 28456 261 50 10 1 2 2 2 2 22

输出 2

1036360

数据范围

【样例 $1$ 解释】

以下子集符合要求:$\{a_3,a_4\}$,$\{a_1,a_3,a_4\}$,$\{a_2,a_3,a_4\}$,$\{a_1,a_2,a_3,a_4\}$。

【数据范围】

对于所有数据,$0\le n,m\le 10^6$,$1\le a_i\le 10^6$。

详细数据范围如下表:

测试点编号 $n$ $m$ $a_i$ 每测试点分数
$1$ $=0$     $1$
$2$   $=0$   $1$
$3\sim 6$ $\le 22$     $4$
$7\sim 10$ $\le 1000$ $\le 1000$   $4$
$11\sim 14$     互不相同 $4$
$15\sim 19$ $\le 2\times 10^5$ $\le 2\times 10^5$   $5$
$20\sim 24$       $5$