P4457 [BJOI2018]治疗之雨

    • 240通过
    • 828提交
  • 题目提供者 oscar
  • 评测方式 云端评测
  • 标签 期望 递推 高斯消元 各省省选 2018 北京 O2优化
  • 难度 NOI/NOI+/CTSC
  • 时空限制 4000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    (没玩过《炉石传说》的人可以跳过这一段)今天我们来探讨下《炉石传说》中“治疗之雨”(恢复 $12$ 点生命值,随机分配到所有友方角色上)和“暗影打击装甲”(每当一个角色获得治疗,便对随机敌人造成 $1$点伤害)这两张卡牌之间的互动效果。假设你场上有 $m$个剩余生命值无限大且生命值上限减去剩余生命值也无限大的随从,而对方的场上有 $k$个暗影打击装甲,你的英雄剩余生命值为 $p$、生命值上限为 $n$,现在你使用了一张可以恢复无限多(而不是 $12$ 点)生命值的治疗之雨,问治疗之雨期望总共恢复了几点生命值以后你的英雄会死亡(生命值降为 $0$;治疗之雨的判定机制使得在此后再也不会为英雄恢复生命值)。

    注:题目背景与题目描述有冲突的地方请以题目描述为准

    下面让我们再形式化地描述一遍问题。

    题目描述

    你现在有 $m+1$ 个数:第一个为 $p$,最小值为 $0$,最大值为 $n$;剩下 $m$个都是无穷,没有最小值或最大值。你可以进行任意多轮操作,每轮操作如下:

    在不为最大值的数中等概率随机选择一个(如果没有则不操作),把它加一;

    进行 $k$次这个步骤:在不为最小值的数中等概率随机选择一个(如果没有则不操作),把它减一。

    现在问期望进行多少轮操作以后第一个数会变为最小值 $0$。

    输入输出格式

    输入格式:

    输入包含多组数据。 输入第一行包含一个正整数 $T$,表示数据组数。 接下来 $T$行 ,每行 4个非负整数 $n$、$p$、$m$、$k$(含义见题目描述),表示一次询问。

    输出格式:

    输出 $T$行,每行一个整数,表示一次询问的答案。

    如果无论进行多少轮操作,第一个数都不会变为最小值 $0$,那么输出-1

    否则,可以证明答案一定为有理数,那么请输出答案模 $1000000007$ 的余数,即设答案为 $\frac{a}{b}$($a$、$b$为互质的正整数 ),你输出的整数为 $x$,那么你需要保证 $0 \leq x < 1000000007$且 $a \equiv bx\ mod\ 1000000007$。

    输入输出样例

    输入样例#1: 复制
    2
    2 1 1 1
    2 2 1 1
    输出样例#1: 复制
    6
    8

    说明

    数据范围

    对于 $10\%$ 的数据, $n \leq 3$ ,$m, k \leq 2$ 。

    对于 $20\%$ 的数据, $n, m, k \leq 5$ 。

    对于 $30\%$ 的数据, $n, m, k \leq 30$ 。

    对于 $40\%$ 的数据, $n, m, k \leq 50$ 。

    对于 $50\%$ 的数据, $n, m, k \leq 200$ 。

    对于 $70\%$ 的数据, $n \leq 200$ 。

    对于 $80\%$ 的数据, $n \leq 500$ 。

    对于 $100\%$ 的数据, $1 \leq T \leq 100$,$1 \leq p \leq n \leq 1500$ ,$0 \leq m, k \leq 1000000000$。

    保证不存在$n=p=k=1$,$m=0$的情况(因为出题人判错了)

    保证不存在答案的分母是$1000000007$的倍数的情况(因为出题人没想到)

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