#PQJ225x4114. QOJ 225_4114
QOJ 225_4114
全国青少年信息学奥林匹克
山东省省队选拔赛2015 第一轮 第一试 序列统计 序列统计 【问题描述】 小C 有一个集合S,里面的元素都是小于M 的非负整数。他用程序编写了 一个数列生成器,可以生成一个长度为N 的数列,数列中的每个数都属于集合S。 小C 用这个生成器生成了许多这样的数列。但是小C 有一个问题需要你的 帮助:给定整数x,求所有可以生成出的,且满足数列中所有数的乘积mod M 的 值等于x 的不同的数列的有多少个。小C 认为,两个数列{Ai}和{Bi}不同,当且 仅当至少存在一个整数i,满足Ai≠Bi。另外,小C 认为这个问题的答案可能很 大,因此他只需要你帮助他求出答案mod 1004535809 的值就可以了。 【输入格式】 一行,四个整数,N、M、x、|S|,其中|S|为集合S 中元素个数。 第二行,|S|个整数,表示集合S 中的所有元素。 【输出格式】 一行,一个整数,表示你求出的权值和mod 1004535809 的值。 【样例输入】 4 3 1 2 1 2 【样例输出】 8 【样例说明】 可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、 (2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。 【数据规模和约定】 对于10%的数据,1<=N<=1000; 对于30%的数据,3<=M<=100; 对于60%的数据,3<=M<=800; 对于全部的数据,1<=N<=109,3<=M<=8000,M 为质数,1<=x<=M-1,输 入数据保证集合S 中元素不重复。