P2396 yyy loves Maths VII

    • 306通过
    • 1.3K提交
  • 题目提供者 redbag 管理员
  • 评测方式 云端评测
  • 标签 剪枝 状态压缩,状压 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 228MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    yyy对某些数字有着情有独钟的喜爱,他叫他们为幸运数字;然而他作死太多,所以把自己讨厌的数字成为"厄运数字"

    题目描述

    一群同学在和yyy玩一个游戏

    每次,他们会给yyy n张卡片,卡片上有数字,所有的数字都是"幸运数字",我们认为第i张卡片上数字是ai

    每次yyy可以选择向前走ai步并且丢掉第i张卡片

    当他手上没有卡片的时候他就赢了

    但是呢,大家对"厄运数字"的位置布置下了陷阱,如果yyy停在这个格子上,那么他就输了

    (注意:即使到了终点,但是这个位置是厄运数字,那么也输了)

    现在,有些同学开始问:

    yyy有多大的概率会赢呢?

    大家觉得这是个好问题

    有人立即让yyy写个程序

    "电脑运行速度很快!24的阶乘也不过就620448401733239439360000,yyy你快写个程序来算一算"

    yyy表示很无语,他表示他不想算概率,最多算算赢的方案数,而且是%1,000,000,007以后的值

    大家都不会写程序,只好妥协

    但是这时候yyy为难了,24!太大了,要跑好长时间.

    他时间严重不够!需要你的帮助!

    由于yyy人格分裂,某个数字可能既属于幸运数字又属于厄运数字。

    输入输出格式

    输入格式:

    第一行n

    下面一行n张卡片

    第三行m 表示yyy的厄运数字个数(最多2个)

    最后一行是m个厄运数字

    输出格式:

    方案数%1,000,000,007

    输入输出样例

    输入样例#1: 复制
    8
    1 3 1 5 2 2 2 3
    0
    输出样例#1: 复制
    40320
    输入样例#2: 复制
    24
    1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
    2
    10 15
    
    输出样例#2: 复制
    0

    说明

    数据范围:

    10%的数据n<=10

    50%的数据n<=23

    100%的数据n<=24

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