1

以下代码是我对问题的解决方案： http: //codeforces.com/contest/327/problem/C

我通过循环执行求和的第一部分（因此时间复杂度很差）给出了正确的答案。

即使我认为使用的公式是正确的，我使用几何级数公式的第二部分也会为很多测试用例返回不正确的答案。

我究竟做错了什么？（编辑：- 已确定问题。最后解释）

#include<stdio.h>
#include<string>
#include<vector>
#include<iostream>
typedef long long int lli;

using namespace std;

lli power(lli base, lli exponent)
{
    lli result=1;
    while(exponent)
    {
        if(exponent & 1)
            result=(result*base)%1000000007;
        exponent>>=1;
        base=(base*base)%1000000007;
    }
    return result%1000000007;
}
int main()
{
    string n;
    cin>>n;
    lli k;
    cin>>k;
    vector<int> position;
    for(int i=0;i<n.length();i++)
        if(n[i]=='5' || n[i]=='0')
            position.push_back(i);
    lli m=0;
    for(int i=0;i<position.size();i++)
        m=(m+power(2,position[i]))%1000000007;
    lli answer=0;
    lli l=n.length();

// part1
// the following is finding summation via loop
    for(int i=1;i<=k;i++)
        answer=(answer + (power(2,l*(k-i))*m)%1000000007)%1000000007;
    cout<<answer<<endl;

//part2
// the following finds the sum by using gp formula (1st_term*(ratio^no_of_terms-1)/(ratio-1))    
    answer=1;
    answer=((power(power(2,l),k) - 1)/(power(2,l)-1))%1000000007;
    answer*=m%1000000007;
    cout<<answer<<endl;
    return 0;
}

几个样本输入和输出

输入1：

4555000 3

输出1：

2080638 2080638

输入2：

4555000 8

输出2：

907276560 529323732

编辑：-我已经解决了问题。未定义除法上的模数。幂函数返回幂模 K，其中 K=1000000007。让我们将这个新值称为缩减值。我正在划分两个减少的值。因此，最终答案也少于实际答案。现在我已经确定了他的问题，我仍然不知道如何克服这个问题。

Edit2:- 将第二部分更改为以下作品（在网上找到）。我不知道为什么。

answer=(power(power(2,l),k) - 1);
answer=(answer*power((power(2,l)-1),K-2))%K;
answer=(answer*m)%K;
4

3 回答 3

2

在您的long long int表达式中，您需要确保您的文字常量也是long long int（目前您正在使用int文字常量）。因此，例如更改：

    base=(base*base)%1000000007;

至：

    base=(base*base)%1000000007LL;

更好的是，您不应该在代码中乱扔硬编码常量，而只需定义一个常量并使用它，例如

const long long int K = 1000000007LL;

....

base=(base*base)%K;
于 2013-07-28T18:17:33.340 回答
2

有趣的; 感谢您提出问题并发布修复程序。仅供参考，这是您在做什么的解释：

您可能会看到您已将除以 x（即乘以 1/x）替换为乘以 x^(K-2)。所以问题是：为什么是 K-2？

答案基本上是费马的小定理，它说当你对一个素数 K 进行模乘运算时（而 100000007 是一个素数），那么 x^(K-1) = 1。如果你把它的两边除以 x 那么你得到 x^(K-2) = 1/x。

我希望你能明白这是如何解释你的代码为什么工作的——一方面你有你的 K-2，另一方面是 x。所以提高到 K-2 的幂等于取模 K 的倒数。

例如，考虑以 5 为模（即素数）并将 9 除以 3。

9/3 = 3 和 3%5 = 3 这是我们想要的，但除法可能是个问题：

(9%5)/3 = 4/3 = ? 这是什么意思模5？（这是你的错误）

所以让我们使用 K-2 技巧： 9*(3^(5-2)) = 9*(3^3) = 9*27 = 243 和 243%5 = 3

或者，(9%5) * (3^(5-2)) = 4*(3^3) = 4*27 = 108 和 108%5 = 3

于 2013-07-28T23:32:53.453 回答
0

模运算符 % 在 *= 运算符之前

于 2013-07-28T18:20:12.553 回答