c - SPOJ AGS 运行时错误

Question

我正在 SPOJ 上练习动态规划。我陷入了这个名为 AGS 的问题。下面是我的代码。它在 SPOJ 上出现运行时错误，但在我的计算机上运行得很好。请帮忙

#include<stdio.h>

long long mypow(long long base,long long exp,long long mod,long long log[])
{
    if(log[exp]!=0)
        return log[exp];
    if(exp==0)
        return 1;
    if(exp==1)
        return base%mod;

    long long ans = ((base%mod) * mypow(base,exp-1,mod,log))%mod;
    log[exp]=ans;
    return ans;

}

long long gpsum(long long r,long long k,long long mod,long long log[])
{
    if(k==0)
        return 1;
    if(k==1)
        return 1+r;

    long long ans=(mypow(r,k,mod,log)+gpsum(r,k-1,mod,log))%mod;
    return ans;
}
int main()
{
    long long i,t,k,a,d,r,n,mod,p,q,ans;
   scanf("%lld",&t);

 while(t--)
 {
       scanf("%lld %lld %lld",&a,&d,&r);
       scanf("%lld %lld",&n,&mod);
       long long log[n/2];
       for(i=0;i<n/2;i++)
        log[i]=0;


    if(n==1)
    {
        ans=a;
    }
    else if(n%2==0)
    {
    k=(n-2)/2;
    p=mypow(r,k,mod,log);
    q=gpsum(r,k,mod,log);
    ans=(((p%mod)*(a%mod))%mod+((q%mod)*(d%mod))%mod)%mod;
    }
    else
    {
    k=(n-3)/2;
    p=r*mypow(r,k,mod,log);
    q=r*gpsum(r,k,mod,log);
    ans=(((p%mod)*(a%mod))%mod+((q%mod)*(d%mod))%mod)%mod;
    }

    printf("%lld\n",ans);
 }
return 0;
}

Answer 1

看起来像 long long log[n/2]; 行导致了错误。对于n = 12345678(来自注释中的示例输入)，它将尝试分配大约 6M 的long long，这在堆栈上大约为 50Mb。我猜这对于在线多用户编译器来说太大了。下面的代码将证明这个说法:

#include<stdio.h>

#define MAX 7000000
int main()
{
    volatile long long v[MAX];
    long i;
    for ( i=0; i<MAX; i++ )
        v[i]=i+1;
    printf("Hello");
    return 0;
}

如上所述的 MAX 值将在 ideone 上给出错误。减少该值，例如减少到 700000 将消除错误(不要介意 volatile 和循环练习，它们是为了欺骗优化器)。一个可能的解决方案是静态分配此内存，作为全局变量 - 在主函数之外，这样它将转到 .data 部分，而不是堆栈。这个解决方案:

#include<stdio.h>

#define MAX 7000000
volatile long long v[MAX];
int main()
{

    long i;
    for ( i=0; i<MAX; i++ )
        v[i]=i+1;
    printf("Hello");
    return 0;
}

即使数量较多也能正常工作。