long long int num(int n,int m)
{
long long int k,i;
k=0;
if(n>1)
{
for(i=0;i<=m;i++)
{
k+=((p[i]%MOD)*(num(n-1,i)%MOD))%MOD;
k%=MOD;
}
return k;
}
else
return q[m];
}
上面的代码是在C中,我需要使这个运行得更快,数组p[I],q[I]是全局值,所以是MOD,是否有任何方法我可以使它更快,可能是通过存储值或其他东西。我认为DP可以在这里使用,但我不确定方法。
当我被要求发布p[i]和q[i]和MOD时,它们在这里MOD =1000000000,总是
void seive(int c)
{
long long int i,temp;
p[0]=1;
q[0]=p[0];
for(i=c+1;i<=(2*c+2);i++)
{
temp=((p[i-c-1]%MOD)*(c%MOD))%MOD;
temp/=(i-c);
p[i-c]=((p[i-c-1]%MOD)+(temp%MOD))%MOD;
q[i-c]=((q[i-c-1]%MOD)+(p[i-c]%MOD))%MOD;
}
}
c=m-1(第一个代码中的m和第二个代码中的c是相关的)
声明全局2D- Array。
由于MOD最初没有变化,因此计算p[i]=p[i]%MOD
%操作代价高
long long temp[][]; // size can be max value of n and m and initialize to LLONG_MIN
long long int num(int n,int m) {
long long int k,i;
k=0;
if(n>1)
{
for(i=0;i<=m;i++)
{
int h=0;
if(temp[n-1][i]!= LLONG_MIN){
h=temp[n-1][i];
}else{
temp[n-1][i]= num(n-1,i)%MOD;
h=temp[n-1][i];
}
k+=((p[i])*(h))%MOD;
k%=MOD;
}
return k;
}
else
return q[m];
}