102367: [AtCoder]ABC236 Ex - Distinct Multiples
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Score : $600$ points
Problem Statement
Given are positive integers $N$, $M$, and a sequence of positive integers $D = (D_1, \dots, D_N)$.
Find the number of sequences of positive integers $A = (A_1, \dots, A_N)$ that satisfy the following conditions, modulo $998244353$.
- $1 \leq A_i \leq M \, (1 \leq i \leq N)$
- $A_i \neq A_j \, (1 \leq i \lt j \leq N)$
- For each $i \, (1 \leq i \leq N)$, $A_i$ is a multiple of $D_i$.
Constraints
- $2 \leq N \leq 16$
- $1 \leq M \leq 10^{18}$
- $1 \leq D_i \leq M \, (1 \leq i \leq N)$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$N$ $M$ $D_1$ $\ldots$ $D_N$
Output
Print the answer.
Sample Input 1
3 7 2 3 4
Sample Output 1
3
The three sequences $A$ that satisfy the conditions are $(2, 3, 4), (2, 6, 4), (6, 3, 4)$.
Sample Input 2
3 3 1 2 2
Sample Output 2
0
No sequence $A$ satisfies the conditions.
Sample Input 3
6 1000000000000000000 380214083 420492929 929717250 666796775 209977152 770361643
Sample Output 3
325683519
Be sure to find the count modulo $998244353$.
Input
题意翻译
给定两个正整数 $N,M$ 和一个正整数序列 $D$,询问满足条件的序列 $A$ 的个数: 1. $1\leq A_i\leq M(1\leq i\leq N)$ 2. $A_i\neq A_j(1\leq i<j\leq N)$ 3. $D_i|A_i$ - $2\leq N\leq 16,1\leq M\leq 10^{18},1\leq D_i\leq M$Output
得分:$600$分
问题描述
给定正整数$N$、$M$和一个正整数序列$D = (D_1, \dots, D_N)$。
找出满足以下条件的正整数序列$A = (A_1, \dots, A_N)$的数量,取模$998244353$。
- $1 \leq A_i \leq M \, (1 \leq i \leq N)$
- $A_i \neq A_j \, (1 \leq i \lt j \leq N)$
- 对于每个$i \, (1 \leq i \leq N)$,$A_i$是$D_i$的倍数。
限制条件
- $2 \leq N \leq 16$
- $1 \leq M \leq 10^{18}$
- $1 \leq D_i \leq M \, (1 \leq i \leq N)$
- 输入中的所有值都是整数。
输入
从标准输入以以下格式获取输入:
$N$ $M$ $D_1$ $\ldots$ $D_N$
输出
打印答案。
样例输入 1
3 7 2 3 4
样例输出 1
3
满足条件的三个序列$A$是$(2, 3, 4), (2, 6, 4), (6, 3, 4)$。
样例输入 2
3 3 1 2 2
样例输出 2
0
没有序列$A$满足条件。
样例输入 3
6 1000000000000000000 380214083 420492929 929717250 666796775 209977152 770361643
样例输出 3
325683519
确保找到取模$998244353$后的计数。