1

次のコードは、問題に対する私の解決策です: http://codeforces.com/contest/327/problem/C

ループを介して合計を実行する最初の部分 (したがって、時間の複雑さが悪い) で正しい答えが得られます。

等比数列の式を使用する 2 番目の部分では、使用した式が正しいと思っていても、多くのテスト ケースで間違った答えが返されます。

私は何を間違っていますか？（編集：-問題が特定されました。最後に説明されています）

#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 です。この新しい値を還元値と呼びましょう。私は2つの減らされた値を割っています。したがって、最終的な答えも実際の答えよりも小さくなります。彼の問題を特定したので、これを克服する方法はまだわかりません。

Edit2:- 2 番目の部分を次のように変更すると機能します (オンラインで見つかりました)。理由がわかりません。

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 に答える