高精度的十进制运算

全国奥林匹克信息学联赛虽然最近五年全国奥林匹克信息学复赛中含许多可“一题多解”的试题，但如果按照较优算法标准分类的话，大致可分为

题型题目与课内知识和编程基础相关校门外的树、自由落体、级数求和、乒乓球、麦森数、不高兴的津津、花生采摘、津津的储蓄计划、陶陶摘苹果、循环、谁拿了最多奖学金、2k进制数、数列模拟守望者的逃离、字符串的展开构造法均分纸牌、传染病控制、火星人、篝火晚会、作业调度方案、纪念品分组数据结构字符近似查找、合并果子（堆排序）、栈、FBI树（二叉树）、神经网络（图）、等价表达式（栈）、明明的随机数（快速排序）、Jam的计数法（字串处理）、奖学金（排序）、统计数据（排序）、树网的核（图）枚举法虫食算、侦探推理回溯法选数、字串变换动态规划过河卒、数字游戏、加分二叉树、合唱队形、采药、过河、能量项链、金明的预算方案、开心的金明、双塔问题（高精度）、矩阵取数游戏（高精度）几何计算矩形覆盖联赛的科学性和公信力在增强1、试题的难度和知识结构趋于合理。“抬高门槛、减少偏题”。这两年即没有可直译编程的基础题(最简单的题为排序题或动态规划),亦没有出现非“全军覆没”不可的偏题。2、去年增加了模拟题；新增了排序类试题（普及组是多域数据的排序，提高组要求采用高效的排序算法）；高精度运算首次引入提高组。3、对选手解题能力和综合素质的要求逐年提高。这两年没有单纯的搜索题和可直接套用经典算法的简单题，而数据结构类、构造类和动态规划类的试题增加，以考验选手的数学建模能力和创新意识。4、分数的阶梯层次趋于科学。只懂语言、不懂数据结构和算法的选手拿低分；虽懂编程知识但缺乏数学思维和创新意识的选手拿中等分；综合素质强的选手拿高分（提高组满分的选手不多，因为有一道难度较大的综合题)。高精度运算排序思想及其应用模拟法图论讲座内容高精度运算转换数据类型加法运算减法运算乘法运算除法运算改善高精度运算的效率分析近几年联赛中高精度类的试题数据类型的转换在变量运算对象的数值范围为任何数据类型所无法容纳的情况下,采用整数数组（每一个元素对应一位十进制数，由其下标顺序指明位序号）。1、采用数串形式输入，并将其转化为整数数组。2、用一个整数变量记录数据的实际长度（即数组的元素个数）3、该数组的运算规则如同算术运算。数据结构与转换方法typenumtype=array[1..500]ofword；{整数数组类型}vara，b:numtype；{a和b为整数数组}la，lb:integer；{整数数组a的长度和b的长度}s:string；{输入数串}将数串s转化为整数数组a的方法如下：k←length(s)；fori←1tokdoa[k-i+1]←ord(s[i])-ord(‘0’)；加法运算c←a+b(a、b、c为numtype类型)

vara,b,c:array[1..201]of0..9;n:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputaugend:');readln(n);lena:=length(n);fori:=1tolenadoa[lena-i+1]:=ord(n[i])-ord('0');{加数放入a数组}write('Inputaddend:');readln(n);lenb:=length(n);fori:=1tolenbdob[lenb-i+1]:=ord(n[i])-ord('0');{被加数放入b数组}i:=1;while(i<=lena)or(i<=lenb)dobeginx:=a[i]+b[i]+xdiv10;{两数相加，然后加前次进位}c[i]:=xmod10;{保存第i位的值}i:=i+1end;ifx>=10{处理最高进位}thenbeginlenc:=i;c[i]:=1endelselenc:=i-1;fori:=lencdownto1dowrite(c[i]);writeln{输出结果}end.N进制运算1、当前位规范由mod10改为modn2、进位处理由div10改为div103、运算规则不变求回文数

若一个数（首位不为零）从左向右读与从右向左读都是一样，我们就将其称之为回文数。例如：给定一个10进制数56，将56加65（即把56从右向左读），得到的121是一个回文数。又如，对于10进制数87：STEP1：87+78=165STEP2：165+561=726STEP3：726+627=1353STEP4：1353+3531=4884在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。写一个程序，给定一个N（2≤N≤10，N=16）进制数m，m的位数上限为20。求最少经过几步可以得到回文数。如果在30步以内（包括30步）不可能得到回文数，则输出“impossible”

1.将数串s转化为整数数组m设数串s=s1‥sp，串长为p。其中si为第p-i+1位n进制数（1≤i≤p）。我们将s转化为整数数组m=m[p]‥m[1]，其中m[i]对应第i位n进制数。typemtype=array[1..100]ofinteger；varm：mtype；按下述方法将s转化为整数数组m：p←length(s)；{计算s的串长}fori←1topdo{从最高位开始计算整数数组m}begink←p-i+1；{计算si对应于的m数组下标}cases[i]of{转换si}’a’．．’f’：m[k]←10+ord(s[i])-ord(’a’)；’0’．．’9’：m[k]←ord(s[i])-ord(’0’)；else输出错误信息并退出程序；end；{case}end；{for}2.判别整数数组m是否为回文数functioncheck(m：mtype)：boolean；{若整数数组m为回文数，则返回true，否则返回false}vari：integer；begincheck←false；fori←1todo{返回m非回文数标志}ifm[i]≠m[p-i+1]thenexit；check←true；{返回m为回文数标志}end；{check}3.n进制加法运算整数数组m1与其反序数m2进行n进制加法运算，得到结果m1proceduresolve(varm1：mtype)；varm2：mtype；beginfori←1topdom2[i]←m1[p-i+1]；{计算反序数m2}fori←1topdo{由右而左逐位相加}beginm1[i]←m1[i]+m2[i]；m1[i+1]←；{进位}m1[i]←m1[i]modn；{确定当前位}end；{for}ifm1[p+1]≠0thenp←p+1；{最高位进位}ifcheck(m1)then输出步数并退出程序；end；{solve}4.主程序

输入进制数n和数串s；fillchar(m，sizeof(m)，0)将s转换为整数数组m；ifcheck(m)thenbegin输出步数0；halt；end；{then}步数初始化为0；while步数≤30dobegin步数+1；solve(m)；end；{while}输出无解信息；减法运算c←a-b(a、b、c为numtype类型)

vara,b,c:array[1..200]of0..9;n,n1,n2:string;lena,lenb,lenc,i,x:integer;beginwrite('Inputminuend:');readln(n1);write('Inputsubtrahend:');readln(n2);if(length(n1)<length(n2))or(length(n1)=length(n2))and(n1<n2)thenbegin{n1<n2,结果为负数}n:=n1;n1:=n2;n2:=n;write('-')end;lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');i:=1;while(i<=lena)or(i<=lenb)dobeginifa[i]<b[i]thenbegina[i+1]:=a[i+1]-1;a[i]:=a[i]+10;end;{向高位借位处理}c[i]:=a[i]-b[i];{保存第i位的值}i:=i+1end;lenc:=i;while(c[lenc]=0)and(lenc>1)dodec(lenc);{最高位的0不输出}fori:=lencdownto1dowrite(c[i]);writeln{输出差}end.除法运算1、整数数组除以整数（a←a/i，a为整数数组，i为整数）2、高精度除法x←x/y(被除数x和除数y为整数，解决计算精度和循环节的问题)整数数组除以整数（a←a/i，a为整数数组，i为整数）我们按照由高位到底位的顺序，逐位相除。在除到第j位时，该位在接受了来自j+1位的余数（a[j]←a[j]+(j+1位相除的余数)*10）后与i相除。如果最高位为0（n[ln]=0），则n的长度减1。l←0；{余数初始化}forj←la-1downto0dobegin{按照由高位到底位的顺序，逐位相除}inc(a[j]，l*10)；{接受了来自第j+1位的余数}l←a[j]modi；{计算第j位的余数}a[j]←a[j]divi；{计算商的第j位}end；{for}while(a[la-1]=0)dodec(la)；{计算商的有效位数}高精度除法x←x/y(被除数x和除数y为整数)

高精度运算不仅能够扩大整数的值域，而且能够通过扩大小数的位数来减低除法的精度误差，甚至还可以计算出循环节。设

设小数部分的位数上限为limit；小数部分的指针为len；st为循环节的首指针；s为小数序列，其中s[i]为第i位小数；posi为余数的位序列，其中posi[x]表示余数为x的位序号。记下第1位的余数和小数（posi[xmody]←1，s[1]←（xmody）*10divy，x←xmody）；然后按照除法的运算规则计算第2位、第3位的余数和小数‥‥。若下一位余数x先前出现过（posi[x]<>0），则先前出现的位置posi[x]为循环节的开始（st←posi[x]），退出计算过程；否则依次类推，直至小数位数达到上限limit为止。fillchar(s,sizeof(s),0);{小数部分初始化}fillchar(posi,sizeof(posi),0);{小数值的位序列初始化}len←0;st←0;{小数部分的指针和循环节的首指针初始化}read(x,y);{读被除数和除数}write(xdivy);{输出整数部分}x←xmody;{计算x除以y的余数}ifx=0thenexit;{若x除尽y，则成功退出}whilelen<limitdo{若小数位未达到上限，则循环}begininc(len);posi[x]←len;{记下当前位小数，计算下一位小数和余数}x←x*10;s[len]←xdivy;x←xmody;ifposi[x]<>0{若下一位余数先前出现过，则先前出现的位置为循环节的开始} thenbeginst←posi[x];break;end;{then}ifx=0thenbreak;{若除尽，则成功退出}end;{while}

iflen=0thenbeginwriteln;exit;end;{若小数部分的位数为0，则成功退出；否则输出小数点}write('.');ifst=0{若无循环节，则输出小数部分，否则输出循环节前的小数和循环节}thenfori←1tolendowrite(s[i])elsebeginfori←1tost-1dowrite(s[i]);write('(');fori←sttolendowrite(s[i]); write(')');end;{else}乘法运算1、高精度数组a乘整数I2、两个高精度数组相乘注意：

1、乘积用数组存储，如何定义数组的长度2、乘法过程中，乘积数组的指针如何变化高精度数组a乘整数i设x为当前位相乘的结果和进位x:=x+a[j]*i;{当前位乘积}a[j]:=xmod10;{当前位规整}x:=xdiv10；{计算进位}精确计算n的阶乘n!（7<n<50）……aa[1],a[2],…,a[max]的值可以是0到9的任意数字数组长度为100（因为50!<5050<10050=(102)50=10100，所以50！可以用100个数组元素a[1],a[2],…,a[100]来存放,一个数组元素存放一个数位上的数字。用i表示阶乘中的整数，取值范围在1至50之间，j为数组变量a的下标，取值范围在1至100之间，X存放来自低位的进位数。X

j1009998…321constmax=100;n=20;

vara:array[1..max]of0..9;i,j,k;x:integer;begink:=1;a[k]:=1;{a=1}

fori:=2tondo{a←1*2*3….*n}beginx:=0;{进位初始化}

forj:=1dokdo{a=a*i}beginx:=x+a[j]*i;a[j]:=xmod10;x:=xdiv10

end;

whilex>0do{处理最高位的进位}

begink:=k+1;a[k]:=xmod10;x:=xdiv10

endend;writeln;fori:=kdowento1write(a[i]){输出a}end.乘法运算c←a*b(a、b为numtype类型)

1、积的位数为la+lb-1或者la+lb；2、如果暂且不考虑进位关系，则ai*bj应该累加在积的第j+i-1位上：x:=a[i]*b[j]+xdiv10+c[i+j-1];c[i+j-1]:=xmod10;3、可以先乘、后处理进位vara,b,c:array[1..200]of0..9;n1,n2:string;lena,lenb,lenc,i,j,x:integer;beginwrite('Inputmultiplier:');readln(n1);rite('Inputmultiplicand:');readln(n2);lena:=length(n1);lenb:=length(n2);fori:=1tolenadoa[lena-i+1]:=ord(n1[i])-ord('0');fori:=1tolenbdob[lenb-i+1]:=ord(n2[i])-ord('0');fori:=1tolenado beginx:=0; forj:=1tolenbdo{对乘数的每一位进行处理}beginx:=a[i]*b[j]+xdiv10+c[i+j-1];{当前乘积+上次乘积进位+原数}c[i+j-1]:=xmod10;end;c[i+j]:=xdiv10;{进位}end;lenc:=i+j;while(c[lenc]=0)and(lenc>1)dodec(lenc);{最高位的0不输出}fori:=lencdownto1dowrite(c[i]);writelnend.改善高精度运算的效率

用一个整型数组来表示一个很大的数，数组中的每一个数表示一位十进制数字。这种方法的缺点是，如果十进制数的位数很多，则对应数组的长度会很长，并增加了高精度计算的时间。改善高精度运算效率的两种方法

⑴扩大进制数

⑵建立因子表

优化方法1、扩大进制数一个Longint记录4位数字是最佳的方案。那么这个数组就相当于一个10000进制的数，其中每一个元素都是10000进制下的一位数。

1、数据类型

type

numtype=array[0..9999]oflongint；{整数数组类型，可存储40000位十进制数}

var

a，n:numtype；{a和n为10000进制的整数数组}

st：string；{数串}

la，lninteger；{整数数组a和n的长度}

2、整数数组的建立和输出

当输入数串st后，我们从左而右扫描数串st，以四个数码为一组，将之对应的10000进制数存入n数组中。具体方法如下：

readln(st)；{输入数串st}

k←length(st)；{取得数串st的长度}

fori←0tok-1dobegin{把st对应的整数保存到数组n中}

j←(k-i+3)div4-1；

n[j]←n[j]*10+ord(st[i+1])-48；

end；{for}

ln←(k+3)div4；

当得出最后结果a后，必须按照由次高位（a[la-2]）到最低位（a[0]）的顺序，将每一位元素由10000进制数转换成10进制数，即必须保证每个元素对应四位10进制数。例如a[i]=0015(0≤i≤la-2)，对应的10进制数不能为15，否则会导致错误结果。我们按照如下方法输出a对应的10进制数：

write(a[la-1])；{输出最高位}

fori←la-2downto0do

write(a[i]div1000，(a[i]div100)mod10，(a[i]div10)mod10，a[i]mod10)；

注意⑴、作高精度算术运算时，运算规则不变，但求进位（div10）和当前位（mod10）时，需改为div10000、mod10000。⑵计算整数数组n-1时，从最低的n[0]位出发往左扫描，寻找第一个非零的元素（n[j]≠0，n[j-1]=n[j-2]=…=n[0]=0）。由于该位接受了底位的借位，因此减1，其后缀全为9999（n[j]=n[j]-1，n[j-1]=n[j-2]=…=n[0]=9999）。如果最高位为0（n[ln]=0），则n的长度减1。j←0；{从n[0]出发往左扫描，寻找第一个非零的元素}while(n[j]=0)doinc(j)；dec(n[j])；{由于该位接受了底位的借位，因此减1}fork←=0toj-1don[k]←9999；{其后缀全为9999}if((j=ln-1)and(n[j]=0))thendec(ln)；{如果最高位为0，则n的长度减1}彩票现今，社会上流行着各种各样的福利彩票，彩票已经融入到了人们的日常生活之中。彩票之所以能吸引那么多的人们，玩法多是一大原因。其中有一类是从前N个自然数中选出M个（不计顺序）不同的号码，如果这M个号码与摇奖时摇出的M个中奖号码完全相符，那么就中了头奖。如现在已经有的：30选7，35选7，36选7，37选7……随着时间的推移，越来越多的人不满足于原来的玩法。为了追求更大的刺激，可供选择的号码和每注的号码个数越来越大，88选8，518选18，8888选68等等应运而生。但是，由此也衍生出了许多麻烦。由于数字越来越大，福彩中心的工作人员们已经无法用一般的计数器精确地计算出每一种彩票中头奖的概率。现在请你帮助他们，编一个程序：对于每一种玩法，能够快速准确地计算出中头奖概率的倒数。

输入:n（MN<1040）m（0<M1000）输出：在“N选M”的玩法中，中头奖的概率的倒数。

从N个数中（不计顺序）取出M个不同的数的取法共有C(N，M)种。这里C(N，M)表示组合数。因此，要使摇出的中奖号码与所选的号码完全相同，概率只有1/C(N，M)。所以我们要求的值即为C(N，M)。根据组合数的计算公式：我们可以直接地求解。但是由于题目中的N可能很大，所以我们必须要用到高精度计算。而在高精度计算中，运行的时间与参与运算的数的大小有直接的关系。所以，我们要使运算的中间结果尽可能地小。如果我们先把N~(N-M+1)这M个连续的自然数乘起来，再依次除以1~M就是一种不太明智的选择。1.N和结果a为高精度数组,元素类型为Longint,代表4位一组的数字,即数组相当于一个10000进制的数，其中每一个数都是10000进制下的一位数。2.我们可以先乘N除1，然后乘(N-1)除2，再乘(N-2)除3，……最后乘(N-M+1)除M。因为连续的K个自然数的积一定能被K!整除，所以在这一过程中不会出现除不尽的情况。同时也使得中间结果比较小，从而提高了程序运行的速度。a←1;fori=1tomdobegina←a*n;a←a/i;n←n-1;end;{for}readln(st)；readln(m)；k：=length(st)；{取得数串st的长度}fori：=0tok-1dobegin{把N保存到数组n中}j：=(k-i+3)div4-1；n[j]：=n[j]*10+ord(st[i+1])-48；end；{for}ln：=(k+3)div4；a[0]：=1;la：=1；{初始化数组a}fori：=1tomdobegin{计算组合数C(n，m)}forj：=la-1downto0dobegin{a←a*n}fork：=ln-1downto1doinc(a[j+k]，a[j]*n[k])；a[j]：=a[j]*n[0]；end；{for}l：=0；{规范乘积a}forj：=0tola+ln-1dobegin{处理进位}inc(l，a[j])；a[j]：=lmod10000；l：=ldiv10000；end；{for}

if(a[la+ln-1]<>0){修改a数组的有效位数}theninc(la，ln)elseinc(la，ln-1)；l：=0；{a←a/i}forj：=la-1downto0dobegininc(a[j]，l*1000)；l：=a[j]modi；a[j]：=a[j]divi；end；{for}while(a[la-1]=0)dodec(la)；{修改a数组的有效位数}j：=0；{n←n-1}while(n[j]=0)doinc(j)；dec(n[j])；fork：=0toj-1don[k]：=10000-1；if((j=ln-1)and(n[j]=0))thendec(ln)；{修改n数组的有效位数}end；{for}write(a[la-1])；{输出a}fori：=la-2downto0dowrite(a[i]div1000，(a[i]div100)mod10，(a[i]div10)mod10，a[i]mod10)；优化方法2、乘除时使用因子表任何自然数都可以表示为n=p1k1*p2k2*……*ptkt的形式，p1，p2，……，pt为质因子。设num数组为自然数n，其中num[i]为因子i的次幂数(1≤i≤k)。显然，num[k]，num[k-1]……，num[2]构成了一个自然数，该自然数可以用十进制整数数组ans存储。ans的计算过程如下ans[0]←1；{将num转换为ans}fori←2tokdo{枚举每一个因子}forj←1tonum[i]domultiply(ans，i)；{连乘num[i]个因子i}multiply的过程为高精度十进制运算中的乘法运算（ans←ans*I)有了自然数n的因子表num，可以十分方便地进行乘法或除法运算。例如整数x含有k个因子i，经过乘法或除法后，我们按照上述方法依次处理x的每一个因子，得出的num即为积或商procedureadd(x，ob：longint)；{ob=1，num←num*x；ob=-1，num←num/x}vari：longint；Beginfori←2toxdo{搜索x的每一个因子i}while(xmodi=0)do{计算x含因子i的个数k。num[i]=}begin inc(num[i]，ob)；x←xdivi；end；{while}end；{add}

显然，如果n1=x1*x2*…*xk，则可以通过连续调用add(x1，1)；add(x2，1)；…；add(xk，1)；得出n1对应的因子表num。如果n2=1/(x1,x2…xk)，则可以通过连续调用add(x1，-1)；add(x2，-1)；…；add(xk，-1)；得出n2对应的因子表num。注意，初始时num数组清零。圣诞树

“叮叮当，叮叮当，铃儿响叮当……”一年一度的圣诞节又来临了。今年，霍比特人Timmy打算自己布置一颗圣诞树，瞧，他正往圣诞树上挂彩灯和苹果呢。Timmy的圣诞树是图一的一种形状：这是一棵严格意义上的“二叉树”。然而，将其稍做变化如图二所示，就可以变成另一种形状不同的圣诞树！Timmy一下来了兴趣，他有N个彩灯或苹果要挂在圣诞树上，因此，圣诞树必须有且仅有N个节点。你能帮助Timmy统计出这样的“圣诞树”一共有多少种么？输入:N（1<N<1000）。输出:“圣诞树”的种数。

算法分析

这是一道数值统计的题目。用F(N)表示N个节点的二叉树一共有多少种。我们不妨假设其左子树有i个节点，右子树就有N-i-1个节点。那么，不难得出一个简单的公式：

用这个公式就能求出所要的答案了。但是，问题中N规模很大，达到了1000！其计算过程中免不了要涉及到高精度加法和乘法计算。用这个公式的解决问题的时间效率自然就不高。我们必须寻找到另一种更快的计算方法。这实际上是一个经典的Catalan数模型。公式：许多看似不相关的问题和Catalan数都有密切的联系1、火车站的栈道问题（分区联赛出现过）2、一只蜗牛在一个N*M的网格上爬行，它从（1，1）开始，目标是（N，M）每次它可以往下或者往右爬行，但是蜗牛只能在白色区域爬行，不允许闯入灰色区域的点。问蜗牛有多少种不同的爬行方法到达目的地（数据的规模是1≤N≤M≤3000）。

read(n)；{输入彩灯或苹果数}fillchar(num，sizeof(num)，0)；fori：=0tondo{计算}begin add(i+1，-1)；{num←num*} add(n+n-i，1)；end；{for}add(n+1，-1)；{计算/(n+1)}fillchar(ans，sizeof(ans)，0)；ans[0]：=1；{将num转换为ans} fori：=2toLIMITdo{枚举每一个因子}forj：=1tonum[i]domult(ans，i)；{乘入因子i}fori：=LIMITdownto0do{输出}if(ans[i]>0)then{若i位是最高位，则输出解} begin forj：=idownto0dowrite(ans[j])； writeln；end；{then}变量num和过程add的定义如前所述。分析近几年联赛中

高精度类的试题Hanoi双塔问题【问题描述】给定A,B,C三根足够长的细柱，在A柱上放有2n个中间有空的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的(下图为n=3的情形）。现要将这些圆盘移到C柱上，在移动过程中可放在B柱上暂存。要求:

(1)每次只能移动一个圆盘；

(2)A、B、C三根细柱上的圆盘都要保持上小下大的顺序；

任务:设An为2n个圆盘完成上述任务所需的最少移动次数，对于输入的n，输出An。

【输入】输入文件hanoi.in为一个正整数n，表示在A柱上放有2n个圆盘。

【输出】输出文件hanoi.out仅一行，包含一个正整数，为完成上述任务所需的最少移动次数An。

递推关系式

设f[i]代表i个尺寸的盘子移动到目标柱的最少步数。移动分三个步骤：把前i-1尺寸的个盘子由起始柱移动到中间柱，移动步数为f[i-1]；把第i个尺寸的盘子由起始柱移动到目标柱，移动步数为f[i]=2；把前i-1个尺寸的盘子由中间柱移动到目标柱，移动步数为f[i-1]因此递推关系式为：f[i]=f[i-1]*2+2=(2≤i≤n)

边界：f[1]=2由于n的上限为200，因此需要采用高精度加法和高精度乘法运算。为了确保不超时，建议按照104进制存储。

readln(n);{读盘子的尺寸数}fillchar(f,sizeof(f),0);f[1,0]:=1;f[1,1]:=2;{f[1]=2}fori:=2tondo{计算f[i]=f[i-1]*2+2}beginf[i]:=f[i-1]*2;f[i]:=f[i]+2;end;write(f[n,f[n,0]]);{输出最高位}fori:=f[n,0]-1downto1do{按照max进制格式输出中间位}beginiff[n,i]<1000thenwrite(0);iff[n,i]<100thenwrite(0);iff[n,i]<10thenwrite(0);write(f[n,i]);end;writeln;矩阵取数游戏

【问题描述】帅帅经常跟同学玩一个矩阵取数游戏：对于一个给定的n*m的矩阵，矩阵中的每个兀aij均为非负整数。游戏规则如下：l每次取数时须从每行各取走一个元素，共n个。m次后取完矩阵所有元素；2每次取走的各个元素只能是该元素所在行的行首或行尾；3每次取数都有一个得分值，为每行取数的得分之和，每行取数的得分=被取走的元素值*2i，其中i表示第i次取数(从l开始编号)；4游戏结束总得分为m次取数得分之和。帅帅想请你帮忙写一个程序，对于任意矩阵，可以求出取数后的最大得分。【输入】输入文件game．in包括n+1行：第l行为两个用空格隔开的整数m和m。第2-n+l行为n*m矩阵，其中每行有m个用单个空格隔开的非负整数。【输出】输出文件game．out仅包含1行，为一个整数，即输入矩阵取数后的最大得分。【限制】60％的数据满足：1≤n，m≤30，答案不超过1016100％的数据满足：l<n，m≤80，0≤aij≤1000给出一个N*M的矩阵，每次取每行的行首和行末的一个数，得分=被取走的元素值*2i（i表示第i次取数）。求最大得分。动态规划。对每行分别处理求最大得分。定义F[i,j]表示当前从某行的第i个元素取到第j个元素的最大得分。有两种取法：取末尾的第j个元素，得分为（F[i,j-1]+G[j]）*2；取首部的第i个元素，得分为(F[i+1,j]+G[i])*2；显然F[i,j]=max(F[i,j-1]+G[j]，F[i+1,j]+G[i])*2。边界：F[i,i]=G[i]*2。（1≤i≤m）当前行的最大得分为F[1,m]。累加n行的最大得分即为问题解。注意：由于最终答案位数在30位左右，需要高精度计算。为了确保不超时，建议按照106进制存储。计算s行的状态转移方程functioncalc(s:longint):anstype;vari,j,l:longint;temp1,temp2:anstype;beginfillchar(f,sizeof(f),0);｛状态转移方程初始化为０｝fori:=1tomdof[i,i]:=map[s,i]*2;｛f[i,i]为s行的第i个元素值＊２｝

forl:=2tomdo｛枚举区间长度｝fori:=1tom-l+1do｛枚举区间首指针｝beginj:=i+l-1;｛计算尾指针｝temp1:=(f[i+1,j]+map[s,i])*2;｛取区间首元素｝temp2:=(f[i,j-1]+map[s,j])*2;｛取区间尾元素｝iftemp1≥temp2｛取两个方案的大者作为该区间的状态转移方程值｝

thenf[i,j]:=temp1elsef[i,j]:=temp2end;calc:=f[1,m]｛返回s行的状态转移方程值｝end;主程序

readln(n,m);｛读矩阵规模｝fori:=1tondo｛读矩阵元素（存储方式为高精度数组）｝forj:=1tomdobeginmap[i,j][0]:=1;read(map[i,j][1])；end;fillchar(ans,sizeof(ans),0);｛最大得分初始化为０｝fori:=1tondoans:=ans+calc(i);{累加n行的状态转移方程值｝write(ans[ans[0]]);｛输出最大得分的最高位｝fori:=ans[0]-1downto1do｛按照由高至低的顺序输出每一位值｝beginstr(ans[i],st);｛将最大得分的第i位转化为数串｝whilelength(st)<limitldoinsert('0',st,1);｛第i位实际位数不足８位，串首添‘０’｝write(st)｛输出第i位｝end;麦森数【问题描述】形如2P-1的素数称为麦森数，这时P一定也是个素数。但反过来不一定，即如果P是个素数，2P-1不一定也是素数。到1998年底，人们已找到了37个麦森数。最大的一个是P=3021377，它有909526位。麦森数有许多重要应用，它与完全数密切相关。任务：从文件中输入P（1000<P<3100000），计算2P-1的位数和最后500位数字（用十进制高精度数表示）【输入格式】文件中只包含一个整数P（1000<P<3100000）【输出格式】第一行：十进制高精度数2P-1的位数;第2-11行：十进制高精度数2P-1的最后500位数字。（每行输出50位，共输出10行，不足500位时高位补0）不必验证2P-1与P是否为素数。使用倍增思想，优化幂运算首先，看一个简单的例子——已知整数a，计算a17。很显然，一种最简单的方法就是令b=a，然后重复16次进行操作b=b*a。这样，为了得到a17，共进行了16次乘法。现在考虑另外一种方法，令a0=a，a1=a2，a2=a4，a3=a8，a4=a16，可以看出，ai=ai-12，(1≤i≤4)。于是，得到a0，a1，a2，a3，a4共需要4次乘法。而a17=a*a16=a0*a4，也就是说，再进行一次乘法就可以得到a17。这样，总共进行5次乘法就算出了a17。已知a，计算an:

将n表示成为二进制形式，并提取出其中的非零位，即n=2(b1)+2(b2)+……+2(bw)，(2(i)=2i)不妨设b1<b2<……<bw。例如n=9，b2=3，b1=0由于已知a，所以也就知道了a0，重复bw次将这个数平方并记录下来，就可以得到(bw+1)个数：a2(0)，a2(1)，a2(2)，……，a2(bw)；根据幂运算的法则，可以推出an=a2(b1)+2(b2)+..2(bw)，=a2(b1)*a2(b2)*……*a2(bw)，而这些数都已经被求出，所以最多再进行(bw+1)次操作就可以得到。算法分析

1、2P-1的位数为2、采用高精度运算计算和输出2P-1的最后500位数字。设ans为2p-1对应的高精度数组；我们将p转换为对应的二进制数Dn…D0，其中Di的权为2i。==()2。将p对应二进制数中值为1的权2i作为2的次幂，组成ans=2P-1的一项()，显然，后一项为前一项的平方。当前项存储在高精度数组I中，取后500位。p=ans=2p-1=-1=-1。我们将p对应二进制数中值为1的每一项连乘起来，每一次的乘积取后500位，最后的乘积ans-1即为2p-1对应的高精度数组。主程序read(p);{输入2的乘幂数}writeln(trunc(p*ln(2)/ln(10)+1));{计算和输出2p-1的位数}fillchar(l,sizeof(l),0);l[0]:=2;{当前项初始化}fillchar(ans,sizeof(ans),0);ans[0]:=1;{乘积项初始化}whilep>0do{由低位向高位方向逐位分析p的每一个二进制位}beginifpmod2=1若p的当前二进制位为1，则连乘当前项，取乘积的后500位}then{beginans←ans*l；end;{then}p:=pdiv2;{处理高一位}

l←l2；

end;{while}dec(ans[0]);{计算2p-1}fori:=499downto0do{按照50位数一行的格式输出2p-1的后500位数}beginwrite(ans[i]);ifimod50=0thenwriteln;end;{for}

循环【问题描述】乐乐是一个聪明而又勤奋好学的孩子。他总喜欢探求事物的规律。一天，他突然对数的正整数次幂产生了兴趣。众所周知，2的正整数次幂最后一位数总是不断的在重复2，4，8，6，2，4，8，6……我们说2的正整数次幂最后一位的循环长度是4（实际上4的倍数都可以说是循环长度，但我们只考虑最小的循环长度）。类似的，其余的数字的正整数次幂最后一位数也有类似的循环现象：循环循环长度22、4、8、6433、9、7、1444、6255166177、9、3、1488、4、2、6499、12这时乐乐的问题就出来了：是不是只有最后一位才有这样的循环呢？对于一个整数n的正整数次幂来说，它的后k位是否会发生循环？如果循环的话，循环长度是多少呢？注意：1．

如果n的某个正整数次幂的位数不足k，那么不足的