省选模拟赛

提示:计数不取模,爆零两行泪.

不同还倍数

题目描述

给定两个正整数 \(N,M\) ,和一个序列 \(Z=(Z_1,....,Z_N)\) .
求出满足以下要求的序列 \(T=(T_1,....,T_N)\) 的个数,答案对 \(998244353\) 取模.

• \(1 \leq T_i \leq M\ \ \ \ (\forall 1 \leq i \leq N)\)
• \(T_i \not = T_j\ \ \ \ \ (\forall 1 \leq i < j \leq N)\)
• \(\forall 1 \leq i \leq N \ \ \ \ \ \ \ T_i 是Z_i 的倍数\)

输入格式

第一行两个正整数 \(N,M\), 接下来一行 \(N\) 个正整数 \(D_1,...,D_N\)

输出格式

一个正整数表示答案,对 \(998244353\) 取模.

数据范围

• 对于前 \(30 \%\),满足 \(2 \leq N \leq 7, 1 \leq M \leq 10\)

• 对于另外 \(20\%\), 满足 \(N \leq 10\)

• 对于所有的数据,满足 \(2 \leq N \leq 16, 1 \leq M \leq 10^{18}, 1 \leq Z_i \leq M(\forall 1 \leq i \leq N )\)

样例

样例输入1

3 7
2 3 4

样例输出1

3

样例1解释

满足条件的序列有 \((2,3,4),(2,6,4),(6,3,4)\)

样例输入2

3 3
1 2 2

样例输出2

0

样例输入3

6 1000000000000000000
380214083 420492929 929717250 666796775 209977152 770361643

样例输出3

325683519

翻倍但异或

起初,你有 \(N\) 封信,每封信上写着一个正整数,你可以执行以任意顺序以下操作任意次.

• 如果你有一封信写着数 \(X\),你可以拥有一封写着 \(2X\) 的信.

• 如果你有一封信写着数 \(X\),另一封写着数 \(Y\) ,你可以拥有一封写着 \(\rm X \ \ \mathcal{XOR} \ \ \rm Y\) 的数信.

拥有新的信的同时,你原来的信不会消失.

但是,由于 \(\rm happyguy\)倡导节约,所以 \(\rm happyguy\) 想知道最多能有多少个不超过 \(M\) 的数字可以被写在信上,答案对 \(998244353\) 取模.

输入格式

第一行两个正整数 \(N,M\), 接下来一行 \(N\) 个正整数 \(Z_i\),代表初始你拥有的信上面的数字, 不保证不会超过 \(M\).

注意, \(M\) 和初始的数字会以二进制的形式给出.

输出格式

一个正整数表示答案,对 \(998244353\) 取模.

数据范围

• 对于前 \(30 \%\),满足 \(N=1\)

• 对于另外 \(20 \%\) ,满足 \(M,Z_i \leq 2^{31}\)

• 对于所有的数据,满足 \(1 \leq N \leq 6, 1 \leq M \leq 2^{4000}, 1 \leq Z_i \leq 2^{4000}(\forall 1 \leq i \leq N )\)

样例

样例输入1

3 111
1111
10111
10010

样例输出1

4

样例1解释

0,3,5,6可以被写在信上,提供一种可以拥有6的方式

• 15 -> 30

• 30,18 -> 12

• 12->24

• 30,24 -> 6

样例输入2

4 100100
1011
1110
110101
1010110

样例输出2

37

样例输入3

4 111001100101001
10111110
1001000110
100000101
11110000011

样例输出3

1843

样例输入4

1 111111111111111111111111111111111111111111111111111111111111111
1

样例输出4

466025955

C.钝角

黑板上有 \(N\) 个 \(0\), \(M\) 个 \(1\) ,每次操作你可以任意选择 \(K\) 个黑板上的数,擦掉他们并且把他们的平均数(有理数)写在黑板上.

数据保证若干次操作后黑板上只剩一个数,问最后黑板上可以写下多少种有理数,答案对 \(1e9+7\) 取模.

输入格式

一行三个正整数 \(N,M,K\)

输出格式

一个正整数表示答案,对 \(1e9+7\) 取模.

数据范围

• 对于前 \(30 \%\),满足 \(2 \leq N, M \leq 10\)

• 对于所有的数据,满足 \(1 \leq N,M\leq 2000, 2 \leq K \leq 2000, N+M-1是 K-1的倍数\)

样例

样例输入1

2 2 2

样例输出1

5

样例1解释

满足条件的序列有 \(\frac 1 4, \frac 3 8 ,\frac 1 2, \frac 5 8 , \frac3 4\)

样例输入2

3 4 3

样例输出2

9

样例输入3

150 150 14

样例输出3

937426930