数学 - Page 18 - hzwer.com

「wiki1281」Xn数列
题目描述 Description给你6个数，m,a,c,x0,n,gXn+1 =(aXn +c)modm，求Xnm,a,c,x0,n,g<=10^18输入描述 InputDescription一行六个数 m,a,c,x0,n,g输出描述 OutputDescription输出一个数 Xn modg样例输入 SampleInput1187153样例输出 SampleOutput2数据范围及提示 DataSize&Hintint64按位相乘可以不要用高精度。题解由题目中Xn+1 =(a*Xn +c)%m可得以下矩阵：┏a,0┓[Xn,c]*┃ ┃=[Xn+...
02014年3月3日3,395递推与动规,矩阵乘法

「POJ3070」Fibonacci
DescriptionIntheFibonacciintegersequence, F0 =0, F1 =1,and Fn = Fn −1 + Fn −2 for n ≥2.Forexample,thefirsttentermsoftheFibonaccisequenceare:0,1,1,2,3,5,8,13,21,34,…AnalternativeformulafortheFibonaccisequenceis.Givenaninteger n,yourgoalistocomputethelast4digitsof Fn.InputTheinputtestfilewillcontainmultipletestcases.Eachtestcaseconsistsofasinglelinecontainingn(wh...
02014年3月3日5,158递推与动规,矩阵乘法
「POJ2262」Goldbach’s Conjecture
DescriptionIn1742,ChristianGoldbach,aGermanamateurmathematician,sentalettertoLeonhardEulerinwhichhemadethefollowingconjecture:Everyevennumbergreaterthan4canbewrittenasthesumoftwooddprimenumbers.Forexample:8=3+5.Both3and5areoddprimenumbers.20=3+17=7+13.42=5+37=11+31=13+29=19+23.Todayitisstillunprovenwhethertheconjectureisright.(Ohwait,Ihavetheproofofcourse,butitistoolongtowriteitonthem...
22014年2月28日3,875筛法
「POJ1740」A New Stone Game
DescriptionAliceandBobdecidetoplayanewstonegame.Atthebeginningofthegametheypickn(1<=n<=10)pilesofstonesinaline.AliceandBobmovethestonesinturn.Ateachstepofthegame,theplayerchooseapile,removeatleastonestones,thenfreelymovestonesfromthispiletoanyotherpilethatstillhasstones.Forexample:n=4andthepileshave(3,1,4,2)stones.Iftheplayerchosethefirstpileandremoveone.Thenitcanreachthefollowstat...
02014年2月27日3,335博弈论
「POJ2234」Matches Game
DescriptionHereisasimplegame.Inthisgame,thereareseveralpilesofmatchesandtwoplayers.Thetwoplayerplayinturn.Ineachturn,onecanchooseapileandtakeawayarbitrarynumberofmatchesfromthepile(Ofcoursethenumberofmatches,whichistakenaway,cannotbezeroandcannotbelargerthanthenumberofmatchesinthechosenpile).Ifafteraplayer’sturn,thereisnomatchleft,theplayeristhewinner.Supposethatthetwoplayersareallverycle...
02014年2月27日3,746博弈论
「BZOJ1076」[SCOI2008] 奖励关
Description你正在玩你最喜欢的电子游戏，并且刚刚进入一个奖励关。在这个奖励关里，系统将依次随机抛出k次宝物，每次你都可以选择吃或者不吃（必须在抛出下一个宝物之前做出选择，且现在决定不吃的宝物以后也不能再吃）。宝物一共有n种，系统每次抛出这n种宝物的概率都相同且相互独立。也就是说，即使前k-1次系统都抛出宝物1（这种情况是有可能出现的，尽管概率非常小），第k次抛出各个宝物的概率依然均为1/n。获取第i种宝物将得...
12014年2月7日8,076状压动规,概率与期望
「JoyOI1118 – 1119」a^b1 – 2
a^b描述Description求a^b由于结果可能很大，我们现在只需要知道这个值mod 1012就可以了（为什么是1012？我的生日）a<1000000b<1000000输入格式InputFormat第一行两个数 a b输出格式OutputFormat一行，就是mod 1012的值样例输入SampleInput22样例输出SampleOutput4代码快速幂[crayon-6769b38569498887023681/]1119有多组数据[crayon-6769b385694a0491795649/] ...
02014年1月27日2,725快速幂
「CODEVS1851」越狱
题目描述 Description监狱有连续编号为1...N的N个房间，每个房间关押一个犯人，有M种宗教，每个犯人可能信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱输入描述 InputDescription输入两个整数M，N.1<=M<=10^8,1<=N<=10^12输出描述 OutputDescription可能越狱的状态数，模100003取余样例输入 SampleInput23样例输出 SampleOutput6数据范围及提示 Dat...
02014年1月5日3,958快速幂
「vijos1196」吃糖果游戏
描述Matrix67和Shadow正在做一个小游戏。桌子上放着两堆糖果，Matrix67和Shadow轮流对这些糖果进行操作。在每一次操作中，操作者需要吃掉其中一堆糖果，并且把另一堆糖果分成两堆（可以不相等）留给对方操作。游戏如此进行下去，糖果数会越来越少，最后必将出现这样一种情况：某人吃掉一堆糖果后发现另一堆里只剩一块糖果不能再分了。游戏规定此时该操作者吃掉最后这一块糖果从而取胜。这个游戏是不公平的。对于任意一种初始状...
02013年12月19日3,922博弈论
「vijos1655」萌萌的糖果博弈
背景用糖果来引诱小朋友学习是最常用的手法，绵羊爸爸就是用糖果来引诱萌萌学习博弈的。描述他把糖果分成了两堆，一堆有A粒，另一堆有B粒。他让萌萌和他一起按照下面的规则取糖果：每次可以任意拿走其中一堆糖果；如果这时候另一堆糖果数目多于1粒，就把它任意分成两堆，否则就把剩下的一粒糖果取走并获得这次博弈的胜利。胜利者将获得所有的糖果。萌萌想要得到所有的糖果，而绵羊爸爸想把糖果留下以便下一次利用。现在由萌萌先取...
02013年12月19日3,564博弈论
NOIP2003栈(卡特兰数)
题目描述栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的...
02013年11月17日18,002卡特兰数
NOIP2013转圈游戏
描述n个小伙伴（编号从0到n-1）围坐一圈玩游戏。按照顺时针方向给n个位置编号，从0到n-1。最初，第0号小伙伴在第0号位置，第1号小伙伴在第1号位置，……，依此类推。游戏规则如下：每一轮第0号位置上的小伙伴顺时针走到第m号位置，第1号位置小伙伴走到第m+1号位置，……，依此类推，第n−m号位置上的小伙伴走到第0号位置，第n-m+1号位置上的小伙伴走到第1号位置，……，第n-1号位置上的小伙伴顺时针走到第m-1号位置。现在，一共进行...
02013年11月16日6,281快速幂