题目名称	1981. [SDOI 2015] 序列统计
输入输出	`sdoi2015_sequence.in/out`
难度等级	★★★★
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	10
题目来源	cstdio 于2015-05-15加入
开放分组	全部用户
提交状态
分类标签	FFT 数学 NTT 快速幂
	分享题解

通过：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楼
回复 @TenderRun : $S_i\ge 0$ 好凶残,不考虑这个只过2点 YGOI_真神名曰驴蛋蛋 2017-01-10 08:50 11楼
竟然没有x=0的情况 TenderRun 2016-08-22 14:11 10楼
为什么我的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楼
回复 @Asm.Def : Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz 常数什么的说多了都是泪…… cstdio 2015-05-26 15:53 6楼
回复 @cstdio : Orz……其实早就忘光了，来复习一下…… Asm.Def 2015-05-26 14:40 5楼
原根都能求错。。天一阁 2015-05-23 10:54 4楼
这时限给的不(tai)对(jin)呀，应该是3s吧（常数杀） update：为啥还是T辣请容我cheat一组。呜呜，我的NTT好慢天一阁 2015-05-22 21:52 3楼

1981. [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输出】

【样例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$ 中元素不重复。