c - 反回文字符串

Question

实际上这是来自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;
}

程序的任何一次运行可能需要处理最多 10⁵ N、M 对，其中 N code> 和 M 各在 1 到 10⁹ 之间。

Answer 1

Please help me which part makes my code slower.

没有太多需要考虑的部分。一般来说，I/O 比计算慢得多，但是您没有超过需要的 I/O，所以我们暂时忽略它。

然后考虑您的 anti_palindrome() 函数。一般情况下，它会循环 N 次，在每次迭代中执行三个算术运算和两次赋值。对于每次迭代来说，这并不昂贵，但每个测试用例可能有十亿次迭代，一万个测试用例，总共大约有 5x10¹⁴ 混合操作。这些操作将花费几秒钟以上的时间。

当我这样做时，我发现你的算法无论如何都是错误的。您应该报告以 10⁹ + 7 为模的结果，但在计算结束之前很久，您就会溢出 prod 变量。由此产生的行为是未定义的。如果 prod 具有无符号类型，则将定义行为，但仍然是错误的。切换到 pow() 而不是循环会极大地提高性能，但不能解决这个问题。你需要一些更聪明的东西。