P3726 [AH2017/HNOI2017]抛硬币

    • 126通过
    • 575提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 各省省选 2017 安徽 湖南 O2优化 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    小 A 和小 B 是一对好朋友,他们经常一起愉快的玩耍。最近小 B 沉迷于**师手游,天天刷本,根本无心搞学习。但是已经入坑了几个月,却一次都没有抽到 SSR,让他非常怀疑人生。勤勉的小 A 为了劝说小 B 早日脱坑,认真学习,决定以抛硬币的形式让小 B 明白他是一个彻彻底底的非洲人,从而对这个游戏绝望。两个人同时抛 b 次硬币,如果小 A 的正面朝上的次数大于小 B 正面朝上的次数,则小 A 获胜。

    但事实上,小 A 也曾经沉迷过拉拉游戏,而且他一次 UR 也没有抽到过,所以他对于自己的运气也没有太大把握。所以他决定在小 B 没注意的时候作弊,悄悄地多抛几次硬币,当然,为了不让小 B 怀疑,他不会抛太多次。现在小 A 想问你,在多少种可能的情况下,他能够胜过小 B 呢?由于答案可能太大,所以你只需要输出答案在十进制表示下的最后 k 位即可。

    输入输出格式

    输入格式:

    有多组数据,对于每组数据输入三个数a,b,k,分别代表小A抛硬币的次数,小B抛硬币的次数,以及最终答案保留多少位整数。

    输出格式:

    对于每组数据,输出一个数,表示最终答案的最后 k 位为多少,若不足 k 位以 0 补全。

    输入输出样例

    输入样例#1: 复制
    2 1 9
    3 2 1
    输出样例#1: 复制
    000000004
    6

    说明

    对于第一组数据,当小A抛2次硬币,小B抛1次硬币时,共有4种方案使得小A正面朝上的次数比小B多。

    (01,0), (10,0), (11,0), (11,1)

    对于第二组数据,当小A抛3次硬币,小B抛2次硬币时,共有16种方案使得小A正面朝上的次数比小B多。

    (001,00), (010,00), (100,00), (011,00), (101,00), (110,00), (111,00), (011,01), (101,01), (110,01),(111,01), (011,10), (101,10), (110,10), (111,10), (111,11).

    数据范围

    10%的数据满足a,b≤20;

    30%的数据满足a,b≤100;

    70%的数据满足a,b≤100000,其中有20%的数据满足a=b;

    100%的数据满足$1\le a,b\le 10^{15},b\le a\le b+10000,1\le k\le 9$,数据组数小于等于10。

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