| 题目名称 | 1981. [SDOI 2015] 序列统计 |
|---|---|
| 输入输出 | sdoi2015_sequence.in/out |
| 难度等级 | ★★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2015-05-15加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：144， 提交：247， 通过率：58.3% | ||||
 winlere |
100 | 0.791 s | 0.00 MiB | C++ |
 Gabriel |
100 | 0.941 s | 1.46 MiB | C++ |
 神利·代目 |
100 | 0.963 s | 6.03 MiB | C++ |
 swm_sxt |
100 | 1.155 s | 0.88 MiB | C++ |
 Rapiz |
100 | 1.272 s | 1.12 MiB | C++ |
 Asm.Def |
100 | 1.276 s | 5.21 MiB | C++ |
 徐戍 |
100 | 1.347 s | 14.38 MiB | C++ |
 schedule |
100 | 1.353 s | 0.70 MiB | C++ |
 小一米 |
100 | 1.359 s | 0.56 MiB | C++ |
|
schedule |
100 | 1.390 s | 0.70 MiB | C++ |
| 本题关联比赛 | |||
| 4043级2023省选模拟赛9 | |||
| 关于 序列统计 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
这就是对我这种背板选手的惩罚...
 hyghb
2018-03-06 20:53
12楼
| ||||
 YGOI_真神名曰驴蛋蛋
2017-01-10 08:50
11楼
| ||||
|
竟然没有x=0的情况
| ||||
|
为什么我的NTT这么慢....
 stdafx.h
2016-03-03 07:26
9楼
| ||||
|
回复 @cstdio :
ORZ  Chenyao2333
2015-05-26 19:57
8楼
| ||||
|
回复 @cstdio :
ORZ  天一阁
2015-05-26 19:30
7楼
| ||||
|
回复 @cstdio :
Orz……其实早就忘光了，来复习一下…… | ||||
|
原根都能求错。。
| ||||
|
这时限给的不(tai)对(jin)呀，应该是3s吧（常数杀）
update：为啥还是T辣  请容我cheat一组。 呜呜，我的NTT好慢 | ||||
TenderRun
cstdio1981. [SDOI 2015] 序列统计
★★★★ 输入文件：sdoi2015_sequence.in
输出文件：sdoi2015_sequence.out
简单对比时间限制：1 s 内存限制：256 MiB
【题目描述】
小 $C$ 有一个集合 $S$，里面的元素都是小于 $M$ 的非负整数。
他用程序编写了一个数列生成器，可以生成一个长度为 $N$ 的数列，数列中的每个数都属于集合 $S$。
小 $C$ 用这个生成器生成了许多这样的数列。但是小 $C$ 有一个问题需要你的帮助：
给定整数 $x$，求所有可以生成出的，且满足数列中所有数的乘积 $mod$ $M$ 的值等于 $x$ 的不同的数列的有多少个。
小 $C$ 认为，两个数列 ${A_i}$ 和 ${B_i}$ 不同，当且仅当至少存在一个整数 $i$，满足 $A_i ≠ B_i$。
另外，小 $C$ 认为这个问题的答案可能很大，因此他只需要你帮助他求出答案 $mod$ $1004535809$ 的值就可以了。
【输入格式】
一行，四个整数，$N、M、x、|S|$，其中 $|S|$ 为集合 $S$ 中元素个数。
第二行，$|S|$ 个整数，表示集合 $S$ 中的所有元素。
【输出格式】
一行，一个整数，表示你求出的权值和 $mod$ $1004535809$ 的值。
【样例1输入】
4 3 1 2 1 2
【样例1输出】
8
【样例2】
点击下载样例2
【数据规模与约定】
对于 $10\%$ 的数据，$1 \leq N \leq 1000$；
对于 $30\%$ 的数据，$3 \leq M \leq 100$；
对于 $60\%$ 的数据，$3 \leq M \leq 800$；
对于全部的数据，$1 \leq N \leq 10^9，3 \leq M \leq 8000$，$M$ 为质数，$1 \leq x \leq M-1$，输入数据保证集合 $S$ 中元素不重复。