P3321 [SDOI2015]序列统计

    • 51通过
    • 157提交
  • 题目提供者洛谷OnlineJudge
  • 标签 快速傅里叶变换,DFT,FFT 概率论,统计 素数判断,质数,筛法 2015 山东 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目描述

    小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的值。

    输入输出样例

    输入样例#1: 复制
    4 3 1 2
    1 2
    输出样例#1: 复制
    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中元素不重复

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。