[AH/HNOI2017]抛硬币

导语

“在我之片子上,我是同等各社长;在自家的心力中,我是平号称打开发者;但是当自我内心,我是一模一样誉为玩家。(On
my business card,I am a corporate president.In my mind, I am a game
developer.But in my heart,I am a gamer.)”

——任天堂社长岩田聪自GDC2005

2015年7月13日,一个特别平常之周一。游戏圈可震荡不安,多寒有名厂商不约而同地于推特上登了深切的凭吊。

SCE全球工作室总裁吉田修平:“祝游戏业界泰斗岩田聪先生同运动好。”

Xbox部门主办Phil
Spencer:“对岩田先生的骨肉、朋友跟全球的玩家来说,这还是凄惶的如出一辙天。他的激情、创意和管理者能力被这个行当更上层楼。”

PlayStation:“谢谢君开的总体,岩田先生。”

CAPCOM:“对岩田先生我们出限度的谢谢和重。他的才情和有趣于咱们这个世界变得重好。”

然,岩田聪,所有任天堂粉丝口中之“聪哥”,自2014年于任天堂官方在线节目“Nintendo
Direct”中留下我们最终一个消瘦的正脸之后,他,人民的好社长,永远的距离了俺们。

到头来,任天堂官方发表新闻稿。讣告:任天堂代表取缔役社长,岩田聪,于2015年7月11日回老家,死因为胆管肿瘤。

岩田聪,一个临危受命的社长,一各项被竞争对手尊敬的娱乐制作人,一各空前之如此让玩家们热衷的首长,他概括而传奇的五十五年人生中,都举行了把什么吧?

题材叙述

小 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
补全。

 

他是同等各可以之玩制作人么?

答案是必然之。

1959年12月6日落地在日本北海道札幌,岩田聪因为大是北海道室兰市市长之因,从小家境不错——当班上大部分同校利用计算器解答数学题的时段,岩田先生却因此Hewlitt
Packard小型计算器编制了外的率先单作品——一个截然无图效果的网球游戏,但就倒是为岩田聪的一日游做生涯奠定了基础。

中学里,岩田聪的均等那个业余爱好便是在老婆做各种电子零件游戏。当中,他采用同光电子计算器发明了几总统简明的数字型游戏。随后,他虽揣在温馨之申将去同学面前炫耀一番,并跟豪门一齐分享其中的欢喜。

1979年,岩田聪大学一致年级。在成功折桂东京工业大学新闻工学系之后,岩田聪没有忘掉自己对游乐支付的热忱,他透过借贷购买了扳平华微机(PET),利用其个别的法力进行编程。大学时代,岩田聪经常会面去东京城厢的某某平电子商城,那里出就东京先是小专卖个人电脑的铺。在那边,他以及那些电脑爱好者成为了情人,并组织了一个俱乐部,他们以秋叶本租了平间店,着手游戏开发,这就是新兴之HAL研究所。(HAL的名源于于库布里克的影《2001高空旅游》中的机器人,同时也出『每个字母都领先IBM一步』的意。)

发端,因为人口短缺,HAL的每个人都得身兼数职。岩田聪在做程序员的以,也使各负其责耍之规划、推广,甚至是扶助大家订餐打扫,但他可乐在其中。随后,进入FC时代,岩田聪因为深谙PET编绘语言,这跟FC主机上的6502系的CPU有平等之地方,导致了岩田聪在编程上占有了生要命之优势——他先后开了《弹珠台》、《高尔夫》和《气球大战》这些老牌作品,并面临了无天堂之推崇,很快的,HAL成为了任天堂的分行。

正逢今日,岩田聪监督并支付的《星的卡于》、《地球冒险》和《任天堂明星大乱斗》等游戏都十分获成功,业界好评如潮,岩田聪也就此让唤醒为HAL的社长。

输入输出样例

输入样例#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).

他是千篇一律号运营妥当,方针是的团队长么?

是的,他是。

2002年5月,任天堂原社长山内溥宣告退休,钦点岩田聪为和谐的后者。就这么,岩田聪成为了世纪一直店任天堂的季无社长,也是会社历史及篇各项非山内家族成员的社长。

每当岩田聪接任前一律年,2001年之任天堂因遭PS2及Xbox的再度夹击,自家的NGC分别在北美和日本市场让抑制,曾也业霸主的任天堂早已风光不再,昔日合力在任天堂周围的老三着开发商纷纷“叛变”,对于直以来呼风唤雨惯了的任天堂来说,这确实是只难以禁的冬季。

岩田聪社长临危受命,针对任天堂内部大刀阔斧,花了通一年的时日做了不管天堂里组织架构,大幅升级开发单位的频率,仅仅以就任第二年就出产了举世最成功之游玩掌机之一之「NDS」,这令至今销量就高达1.5亿令的“超级印钞机”,创新性地引入了“第二屏幕”的概念,触摸屏的进入如相互逻辑变得尤其简易,吸引了再也多之口采购游戏机。

随后,便是「Wii」的降生。游戏机业界受到其的影响上了体感时代,据说,当时在美国,拥有「Wii」游戏主机的家庭还比所有宠物狗的家园还要多。正是「NDS」和「Wii」所组成左右合围的“蓝海计划”,使得任天堂因——面向全年龄的玩家——这样的政策受惠,很快即成为了游戏界的霸主,岩田聪居功至伟,国外知名杂志《Baron》甚至拿他评选也就的天下30那个CEO之一。

数据范围

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 91≤a,b≤1015,b≤a≤b+10000,1≤k≤9,数据组数小于等于10。

转载http://www.cnblogs.com/Yuzao/p/7954245.html

因为 \(a-b\) 很粗,考虑怎么管架子变成和 \(a-b\) 有关.
考虑 \(a=b\) 的景象,赢了转后就输了,平局不到底在内,

只要抽的。减了之后更除。推导如下:

$$\sum_{i=0}^{a}C_a^i * C_a^i =
\sum_{i=0}^{a}C_a^i * C_a^{a-i} = C_{2a}^a$$

平局方案吧C(2a,a)

因此答案为 \((2^{a+b}-C(2a,a))/2\).
\(a>b\) 时,同样存在对称性,对于刚刚着会输,反过来就得到情况,就是 \(2^{a+b}/2\) 种
于刚刚着倒着都赢的景况还尚无算进来:

\[\sum_{i=1}^{b}\sum_{j=1}^{a-b-1}C_{b}^{i}*C_{a}^{i+j}\]
\[\sum_{i=1}^{b}\sum_{j=1}^{a-b-1}C_{b}^{b-i}*C_{a}^{i+j}\]
\[\sum_{j=1}^{a-b-1}C_{a+b}^{b+j}\]
\[\sum_{j=b+1}^{a-1}C_{a+b}^{j}\]
于除2,根据对称性,只算一半即可,注意偶数情况,存在同样起需要手动除2,算2时于因子中减去,算5时一直就逆元即可

取模不是素数,所以如果中国剩余定理

好默认模数为10^9,输出时取模

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 using namespace std;
  6 typedef long long ll;
  7 ll K,fac[6][2000001];
  8 ll exgcd(ll a,ll b,ll &x,ll &y)
  9 {
 10   if (b==0)
 11     {
 12       x=1;y=0;
 13       return a;
 14     }
 15   ll d=exgcd(b,a%b,x,y);
 16   ll t=x;x=y;y=t-(a/b)*x;
 17   return d;
 18 }
 19 ll qpow(ll a,ll b,ll mod)
 20 {
 21   ll res=1;
 22   while (b)
 23     {
 24       if (b&1) res=res*a%mod;
 25       a=a*a%mod;
 26       b/=2;
 27     }
 28   return res;
 29 }
 30 ll rev(ll a,ll b)
 31 {
 32   ll x,y;
 33   exgcd(a,b,x,y);
 34   return (x%b+b)%b;
 35 }
 36 ll calfac(ll x,ll p,ll t)
 37 {
 38   if (x<t) return fac[t][x];
 39   ll s=qpow(fac[t][p-1],x/p,p);
 40   s=(s*fac[t][x%p])%p;
 41   s=(s*calfac(x/t,p,t))%p;
 42   return s;
 43 }
 44 ll lucas(ll b,ll a,ll t,ll p,bool q)
 45 {ll i;
 46   if (b<a) return 0;
 47   ll ap=0,bp=0,cp=0;
 48   for (i=b;i;i/=t) ap+=i/t;
 49   for (i=a;i;i/=t) bp+=i/t;
 50   for (i=b-a;i;i/=t) cp+=i/t;
 51   ap=ap-bp-cp;
 52   if (q==1&&t==2) ap--;
 53   if (ap>=K) return 0;
 54   ll s=qpow(t,ap,p);
 55   ap=calfac(b,p,t);bp=calfac(a,p,t),cp=calfac(b-a,p,t);
 56   s=((s*ap%p)*(rev(bp,p)*rev(cp,p))%p)%p;
 57   if (q&&t==5) s=s*rev(2,p)%p;
 58   return s;
 59 }
 60 ll cal(ll a,ll b,ll Mod,ll pr)
 61 {ll i;
 62   ll ans=qpow(2,a+b-1,Mod);
 63   if (a==b) 
 64     {
 65       ans=(ans-lucas(a+b,a,pr,Mod,1)+Mod)%Mod;
 66       return ans;
 67     }
 68   else 
 69     {
 70       for (i=(a+b)/2+1;i<a;i++)
 71     ans=(ans+lucas(a+b,i,pr,Mod,0)+Mod)%Mod;
 72     }
 73   if ((a+b)%2==0) ans=(ans+lucas(a+b,(a+b)/2,pr,Mod,1)+Mod)%Mod;
 74   return ans;
 75 }
 76 ll work(ll a,ll b,ll k)
 77 {
 78   ll p1=qpow(2,k,2e9+5),p2=qpow(5,k,2e9+5),mod=qpow(10,k,2e9+5);
 79   ll b1=cal(a,b,p1,2),b2=cal(a,b,p2,5);
 80   ll a1=rev(p2,p1),a2=rev(p1,p2);
 81   return (b1*(p2*a1%mod)%mod+b2*(p1*a2%mod)%mod)%mod;
 82 }
 83 void print(ll d,ll k)
 84 {
 85   if (k==1)
 86     printf("%01lld\n",d%qpow(10,1,2e9+5));
 87   if (k==2)
 88     printf("%02lld\n",d%qpow(10,2,2e9+5));
 89   if (k==3)
 90     printf("%03lld\n",d%qpow(10,3,2e9+5));
 91   if (k==4)
 92     printf("%04lld\n",d%qpow(10,4,2e9+5));
 93   if (k==5)
 94     printf("%05lld\n",d%qpow(10,5,2e9+5));
 95   if (k==6)
 96     printf("%06lld\n",d%qpow(10,6,2e9+5));
 97   if (k==7)
 98     printf("%07lld\n",d%qpow(10,7,2e9+5));
 99   if (k==8)
100     printf("%08lld\n",d%qpow(10,8,2e9+5));
101   if (k==9)
102     printf("%09lld\n",d%qpow(10,9,2e9+5));
103 }
104 int main()
105 {ll a,b,k,i,p;
106   fac[2][0]=1;p=qpow(2,9,2e9+5);
107   for (i=1;i<=p-1;i++)
108     if (i%2==0) fac[2][i]=fac[2][i-1];
109     else fac[2][i]=fac[2][i-1]*i%p;
110   fac[5][0]=1;p=qpow(5,9,2e9+5);
111   for (i=1;i<=p-1;i++)
112     if (i%5==0) fac[5][i]=fac[5][i-1];
113     else fac[5][i]=fac[5][i-1]*i%p;
114   while (cin>>a>>b>>k)
115     {
116       K=9;ll d=work(a,b,9);
117       print(d,k);
118     }
119 }

 

他是千篇一律号受玩家崇敬之公众人物么?

不要置疑,毫无疑问。

策上,岩田聪先生带领的任天堂游戏企业,一直是坐劳动玩家的角度出发的。从《马里奥》,到《星的卡于》,再至《口袋妖怪》,任天堂一直奉行着低龄化、大众化的嬉戏制作思路,玩着她们之打,正而孩子一时一般,没有另外暴力的元素,将人们引入快乐的极乐世界,并被人口忍不住陶醉其中。这比现行手游市场,到处充斥在低质、内购的浮躁心截然不同。

私家及,岩田聪先生在媒体上之形象一直是有趣有趣,和蔼可亲,他的所作所为作风也直接是敢做敢当,亲力亲为的。

里面,Nintendo
Direct(任天堂直面会)便是一个雅好的例子。这个由于岩田聪先生主持的在线视频发布会,从
2011 年 10 月 21
日第一企盼诞生至今天,他差点儿每次都亲出现在镜头面前,亲自为“直接”的形式公布游戏新作,无论这些作品是来任天堂,抑或是来第三正值,聪哥都坚持当游戏介绍的解说。「Wii
U
」发售前,聪哥还亲带来开箱视频,为玩家们细微至极地讲解每一个配件的意。

随即被自身回忆了其他一样各业界泰斗,苹果店的创始人及发扬光大者,同样是至了而立之年就是死于癌症的CEO,史蒂夫·乔布斯先生。

引人注目,乔布斯有让人诧异之创造力和想象力,正是他卓越的眼光,才会于乱的市场及芜杂的产品线中找到了那一两个好的想法,并全神贯注地坚持下去;但他啊发生令人心生厌恶的地方——他的切切实实扭曲力场。遇到自己所热爱之,他见面一心一意地坚持;但遇到自己所憎恶的,他会选择性地无视,去回避——这还锻造了外本身可以的至的性格。

同一是当做一个领导人员,作为一个公众形象,岩田聪先生吃人的记忆就使好过多了。我当此处引用岩田聪于2005年GDC游戏大会的客的发言作为参考:

自我生关心玩家的想法。

当我们花费还多之工夫及金来满足玩家的当儿,我们是否遗漏了任何有玩家?

咱出之玩是否吻合各个一个人?

我会问:是否你早就为一舒缓好还无乐意玩的一日游一经挑战自己、辛苦付出为?

自家思念这些问题对于以所得所有人的话都是一个死重要的挑战。

……

自身早已出过一样缓慢名为“任天堂全明星”游戏。那款游戏的人设定使用的是任天堂的经典游戏角色,后来其所出的效果是“震撼”的。但是,当时这个意见并无是流行。因为此前一度发生部分接近的嬉戏出现了。因此,当我们拿此想法提供给任天堂时,公司内外的群口都无扣好她。但是,这次咱们将主要放到了一日游环境的营造上。直到我们的测试员表示来对这款游戏的庞然大物兴趣,公司以前所持有之看法才具备改变。

后来,依次有了底这些工作:

测试游戏之员工开始微笑。

职工开始大笑。

员工高兴地开始相互喊让。

……

以HAL工作遭到,我们找到了将想成为现实性的法门。我们的团体将执自己之想法。我们不见面在发展的道及退。出于这个情怀,我们有着HAL员工非常爱到的各一个人口。

纵然我们来世界之不比地方

即我们说在不同的言语

便我们吃在不同的食物或者饭团

不畏我们当娱乐中发出异之心得

可是今天我们到的每个人有一个好主要的相同点。

以此相同点就是咱都抱有相同的“玩者之内心”。

好望,作为程序员出身的岩田聪,对“人”(也就是玩家们),有着多么深厚的感情;而乔布斯,却再爱将精力倾注在产品上——当然,他创造了独一无二的成功——后果是,他的人际关系一直不好。我思立刻虽是干什么,乔布斯的风评一直褒贬不一,而岩田聪,受到了一边倒之敬重和眷恋的由来之一吧。

后记

说个别单细节:

夫,到了2011年,我们都知晓,任天堂的生活喽得无极端好。因「Wii
U」的计划性既兼顾了轻度玩家与中心玩家,导致了不伦不类、左右两难的地步,让它们并从未如任天堂预期那样成功,为者岩田聪自降
50% 的工钱谢罪。在死庄遭遇,这得说凡是绝无仅有的。

那,岩田聪曾经说了这么一词话:“只要我还以一如既往上,任天堂就不见面举行手游!”当然我们也理解,2015年3月,岩田聪带领任天堂和DeNA携手进军移动产业。

下一场他及世长辞。

作坊间发生这般一种说法:“岩田聪和 DeNA
签的合同,也许是为下同样到社长铺路,下届社长无论是选择继续走这漫长路,还是推翻不倒这漫漫总长,黑锅都是岩田聪自己背了……”

2015年7月13日,就以任天堂官方发完岩田聪逝世的公告后,网友Bakatetu2以推特上披露了一如既往摆放照片——任天堂总部上空还出现了千篇一律鸣彩虹。按道理说,当时日本都城为局部多说话,这种气候是匪轻并发彩虹之。

往深处想,这定是为岩田聪——一各类好人,一各类好社长——游戏业界的免老灵感源泉,踏上彩虹阶梯,进入了玩家的天堂。

发表评论

电子邮件地址不会被公开。 必填项已用*标注