帕斯卡高精度乘法和 N 幂问题

它通常是用倒置数组完成的。

楼上的精度不高。

我会为你写一个乘法。

typearr=array[0..10000]of longint;a[0] 是长度。

function cheng(a,b:arr):arr;

vari,j:longint;

beginfillchar(cheng,sizeof(cheng),0);

for i:=1 to a[0] do

for j:=1 to b[0] do begin

cheng[i+j-1]:=cheng[i+j-1]+a[i]*b[j];

cheng[i+j]:=cheng[i+j]+cheng[i+j-1]mod 10;

cheng[i+j]:=cheng[i+j]div 10;

end;if cheng[a[0]+b[0]]>0 then cheng[0]:=a[0]+b[0] else cheng[0]:=a[0]+b[0]-1;

end;

让我们分解一下：

设字符串的长度为 n，乘数符号为 k，如果 n = 50 且 k = 1，则有 （n-1） = 49 个不同的乘法，当 k = 2 时，有 c（2， 50-1） = 1176 个乘法，即 c（k， n-1） 乘法，当 n 和 k 稍大时，穷举法将不起作用。

设数字字符串为 a1a2...。an

当 k=1：可以在 a1a2 中插入乘数符号时。n-1 个位置，因此我们得到 n-1 个子字符串的乘积：

a1*a2…an,a1a2*a3…an,a1a2…Fortune Bird A（幸运鸟A）

n-1*an

这相当于一种详尽的方法）。

此时的最大值 = 最大值

设 f[i，j] 表示 in。

i 数字。

J乘数符号的最大值G[i，j]表示从AI到AJ的数字列，肢源可以得到动态传递方程：

f[i,j]

max1<=i<=n,1<=j<=k)

边界：f[i，0]。

g[1,i]

序列本身）阶段：子问题是插入 j-1、j-2 ......添加到子字符串中1,0 个乘数符号，因此乘数符号的数量用作阶段（j 阶段）的划分。

状态：随着相乘序列的变化，每个阶段都分为多个状态。

决策：在每个州的每个阶段做出决策。

数据结构：本题对精度要求不高，longint 可用于 pascal）。

intn,k;

n 是数字数，k 是除数*

inti,j,l;

循环变量*

charc;

字符以 * 格式读取

intdata[50]=;

数字数组*

intg[50][50],f[50][10];

g 是数值列，f 是动态规划数组*

初始化：cin

nk;*读取，n，k*

for(i=1;i<=n;i++)cin

c;*读入数字*

data[i]=c-'0';

字符转换为数字*

g[i][i]=data[i];初始化序列*

for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

g[i][j]=g[i][j-1]*10+data[j];

初始化序列*

for(i=1;i<=n;i++)

f[i][0]=g[1][i];

初始化动态规划阵列*

动态规划：for（i=1; i<=n;i++） 方程：f[i，j] 表示将 j * 符号插入前 i 个数字的最佳值。*/

for(j=1;j<=i+1;j++)

for(l=1;l<=i-1;l++)

f[i][j]=max(f[i][j],f[l][j-1]*g[l+1][i]);

输出 f[n][k]。