c - 反回文弦

实际上，这是来自hackerearth的挑战之一。这是问题的链接：https://www.hackerrank.com/challenges/antipalindromic-strings

我以某种方式找到了答案的方法。但是我的代码由于超时而没有被接受。请帮助我，这会使我的代码变慢。

这是我的代码：

int anti_palindrome(long int n,long int m,int mod)
{

    int prod;
    prod=m;
    if(n>1)
        prod=prod*(m-1);
    if(n>2)
    {
        n=n-2;
        while(n)
        {
            prod=prod*(m-2);
            n--;
        }
    }
    return prod%mod;
}

int main()
{
    char scanned[1000];
    int input = 0;
    int T=0;
    int T_cur=0;
    long int N,M;
    char str[1000];
    int mod=1000000007;



    while(fgets(scanned,1000,stdin))
    {
        switch(input)
        {
        case 0:  {
            T=atoi(scanned);
            input=1;
        }
            break;
        case 1: {
            T_cur++;
            strcpy(str,scanned);
            sscanf(str,"%d %d",&N,&M);
            //printf("%lf %lf\n",N,M);
            printf("%d\n",anti_palindrome(N,M,mod));
        }
            break;
        }

        if(T_cur==T)
            break;
    }

    return 0;
}

该程序的任何一次运行都可能需要处理多达105个N，M对，每个N和M在1至109之间。

最佳答案

请帮助我，这会使我的代码变慢。


没有太多要考虑的部分。一般来说，I / O比计算要慢得多，但是您所需要的I / O并不多，因此暂时不考虑它。

然后，考虑您的anti_palindrome()函数。在一般情况下，它循环N次，在每次迭代中执行三个算术运算和两个赋值。以每个迭代为基础，这并不昂贵，但是每个测试用例可能有十亿次迭代，一万个测试用例，总共需要进行5x1014混合操作。该操作数将花费超过几秒钟的时间。

当我这样做时，我发现您的算法仍然是错误的。您应该以109 + 7模的方式报告答案，但是很久才到达计算结尾，您将溢出prod变量。结果行为是不确定的。如果prod具有无符号类型，则将定义行为，但仍然是错误的。切换到pow()而不是循环将极大地提高性能，但不能解决此问题。您需要一些更聪明的东西。

关于c - 反回文弦，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30142253/