矩阵乘法 - Page 2

「泉七培训 – 郑予凡」致命漏洞
对于55%的数据，此题可以用个简单的矩阵乘法100%只要加上高精度即可，但是考场上高精度打萎了只有55%...没发现挂哪了。。。[crayon-6767ed90b0747805666640/] ...
02014年6月14日3,508高精度,矩阵乘法

「BZOJ2510」弱题
Description有M个球，一开始每个球均有一个初始标号，标号范围为1～N且为整数，标号为i的球有ai个，并保证Σai = M。每次操作等概率取出一个球（即取出每个球的概率均为1/M），若这个球标号为k（k < N），则将它重新标号为k +1；若这个球标号为N，则将其重标号为1。（取出球后并不将其丢弃）现在你需要求出，经过K次这样的操作后，每个标号的球的期望个数。Input第1行包含三个正整数N，M，K，表示了标号与球的...
62014年6月6日4,819矩阵乘法
「BZOJ1898」Swamp 沼泽鳄鱼
Description潘塔纳尔沼泽地号称世界上最大的一块湿地，它地位于巴西中部马托格罗索州的南部地区。每当雨季来临，这里碧波荡漾、生机盎然，引来不少游客。为了让游玩更有情趣，人们在池塘的中央建设了几座石墩和石桥，每座石桥连接着两座石墩，且每两座石墩之间至多只有一座石桥。这个景点造好之后一直没敢对外开放，原因是池塘里有不少危险的食人鱼。豆豆先生酷爱冒险，他一听说这个消息，立马赶到了池塘，想做第一个在桥上旅游的...
02014年5月17日5,492递推与动规,矩阵乘法
「NOIP模拟赛」数列
「题目描述」a[1]=a[2]=a[3]=1a[x]=a[x-3]+a[x-1] (x>3)求a数列的第n项对1000000007（10^9+7）取余的值。「输入格式」第一行一个整数T，表示询问个数。以下T行，每行一个正整数n。「输出格式」每行输出一个非负整数表示答案。「样例输入」36810「样例输出」4919「数据范围」对于30%的数据n<=100；对于60%的数据n<=2*10^7；对于100%的数据T<=100，n<=2*10^9；题解这个可以直接矩阵乘法搞掉。。[crayon-6767ed90b...
32014年5月10日4,023递推与动规,矩阵乘法
「BZOJ1009」[HNOI2008] GT考试
Description阿申准备报名参加GT考试，准考证号为N位数X1X2....Xn(0<=Xi<=9),他不希望准考证号上出现不吉利的数字。他的不吉利数学A1A2...Am(0<=Ai<=9)有M位，不出现是指X1X2...Xn中没有恰好一段等于A1A2...Am.A1和X1可以为0Input第一行输入N,M,K.接下来一行输入M位的数。100%数据N<=10^9,M<=20,K<=100040%数据N<=100010%数据N<=6Output阿申想知道不出现不吉利数字的号...
62014年5月9日15,392递推与动规,KMP,矩阵乘法
「BZOJ2326」[HNOI2011] 数学作业
Description题解(F[n]) (10^k 1 1 )(F[n-1])( n )=( 0 1 1 )( n-1 )( 1 ) ( 0 0 1 )( 1 )然后分段矩阵乘法0-9,10-99…10^k-n[crayon-6767ed90b26ec596556432/] ...
52014年4月28日7,250递推与动规,矩阵乘法
「ch30」摆花
背景及描述艺术馆门前将摆出许多花，一共有n个位置排成一排，每个位置可以摆花也可以不摆花。有些花如果摆在相邻的位置（隔着一个空的位置不算相邻），就不好看了。假定每种花数量无限，求摆花的方案数。输入格式输入有1+m行，第一行有两个用空格隔开的正整数n、m，m表示花的种类数。接下来的m行，每行有m个字符1或0,若第i行第j列为1，则表示第i种花和第j种花不能排在相邻的位置，输入保证对称。（提示：同一种花可能不能排在相邻位...
02014年4月5日4,778递推与动规,矩阵乘法
「hdu2294」Pendant
ProblemDescriptionOnSaintValentine'sDay,AleximaginedtopresentaspecialpendanttohisgirlfriendmadebyKkindofpearls.Thependantisactuallyastringofpearls,anditslengthisdefinedasthenumberofpearlsinit.Asisknowntoall,Alexisveryrich,andhehasNpearlsofeachkind.Pendantcanbetoldapartaccordingtopermutationofitspearls.Nowhewantstoknowhowmanykindofpendantcanhemade,withlengthbetween1andN.Ofcour...
02014年3月27日3,037递推与动规,矩阵乘法
「CF400C」Inna and Huge Candy Matrix
InnaandDimadecidedtosurpriseSereja.Theybroughtareallyhugecandymatrix,it'sbigevenforSereja!Let'snumbertherowsofthegiantmatrixfrom 1 to n fromtoptobottomandthecolumns—from 1 to m,fromlefttoright.We'llrepresentthecellontheintersectionofthe i-throwand j-thcolumnas (i, j).Justasisexpected,somecellsofthegiantcandymatrixcontaincandies.Overallthematrixhas p candies:the k-thcandyisa...
02014年3月6日2,870矩阵乘法
「POJ3150」Cellular Automaton
DescriptionA cellularautomaton isacollectionofcellsonagridofspecifiedshapethatevolvesthroughanumberofdiscretetimestepsaccordingtoasetofrulesthatdescribethenewstateofacellbasedonthestatesofneighboringcells.The orderofthecellularautomaton isthenumberofcellsitcontains.Cellsoftheautomatonoforder n arenumberedfrom1to n.The orderofthecell isthenumberofdifferentvaluesitmaycontain.Usually,v...
02014年3月4日4,375递推与动规,矩阵乘法
「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,393递推与动规,矩阵乘法
「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,155递推与动规,矩阵乘法