省选模拟赛
| 题目名称 | 不同还倍数 | 翻倍但异或 | C.钝角 |
|---|---|---|---|
| 输入文件名 | dism.in |
xshit.in |
obtuse.in |
| 输出文件名 | dism.out |
xshit.out |
obtuse.out |
| 每个测试点时间限制 | 2s | 2s | 2s |
| 每个测试点空间限制 | 1Gb | 256Mb | 256Mb |
| 测试点数目 | 10 | 10 | 10 |
| 每个测试点分值 | 10 | 10 | 10 |
提示:计数不取模,爆零两行泪.
不同还倍数
题目描述
给定两个正整数 \(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