1. 首页
  2. 代码宅, 扩展欧几里得, 数学问题

【统计方案】

小B写了一个程序,随机生成了n个正整数,分别是 a[1]..a[n] ,他取出了其中一些数,并把它们乘起来之后模 p ,得到了余数 c 。但是没过多久,小B就忘记他选了哪些数,他想把所有可能的取数方案都找出来。你能帮他计算一下一共有多少种取数方案吗?请把最后的方案数模1000000007后输出。小B记得他至少取了一个数。

输入格式

第一行三个正整数 n,p,c,含义如题目所述。
接下来一行有 n 个正整数,表示生成的 n 个随机数。

输出格式

输出一个数,即方案数模 1000000007 。

样例数据 1

输入

3 7 2
1 2 4

输出

2

样例数据 2

输入

5 7 1
1 1 1 1 1

输出

31

备注

【数据范围】
对于 30% 的数据,n≤16
另有 30% 的数据,p≤10000
对于 100% 的数据,n≤32, p≤10^9, c≤10^9,a[i]<p,p是质数

这道题没看到p是质数考场忘map哭瞎我了,华丽的一个exgcd然后慢慢加TLE了4个点,拿着60分滚蛋了……

正解其实思想差不多,不过因为P是质数,所以不是exgcd而是 求!逆!元!因为逆元唯一算一次就行了,看数据很明显要AC就要折半搜索,先搜出前一半的所有组合存在一个栈中,再搜出后一半组合存在栈中,理论上任选一半把存进去的数放map里统计出现次数再从另一半里枚举求逆元统计即可,跟SDOI计算器那道题很像,然而这道题奇葩了……必须是从前一半里放map从后一半里求逆元,不然有两个点永远WA,而且与答案差70W……至今不知道原因,我选择死亡

下面是我这个蒟蒻的代码,其它大神的代码貌似高级的多……

 

评分 0, 满分 5 星
0
0
看完收藏一下,下次也能找得到
上一篇:
:下一篇

3 条评论

gravatar

*

  1. YYY 1

    那个…我觉得你求逆元的时候好像没注意算出的数是p的倍数的情况…

    #-49楼
    Google Chrome 43.0.2357.130Windows 7
    回复
    stdKonjac真是太蠢辣QAQ
    1. @YYY 难道不是搞一搞同余就行了么……

      Google Chrome 44.0.2403.89Windows 8.1
      回复
      stdKonjac真是太蠢辣QAQ
      1. YYY 1

        @UNknown 一个整数a在模域p下有逆元的条件是a与p互质啊,也就是说如果a是p的倍数那么a在模域p下就没有逆元…
        第87行如果A是C的倍数就应该果断continue…WA也是这个原因吧…

        Google Chrome 43.0.2357.130Windows 7
        回复
        stdKonjac真是太蠢辣QAQ