C++ ABC178C 型の違いだけでWAのものがACになる理由とは？

Question

問題：ABC178C
公式解説
公式解説コード
※すでにAC済みなので解法を知りたいという質問ではありません。

質問

公式解説を見ながら提出してWAとなった原因が分からず、
何故型の違いだけでWAになるのか理由が知りたいので分かる方はご教示ください。
よろしくお願いします。

試したこと

テストケースがまだ公開されていないようでどういったテストケースでWA(WA5/AC15/ALL20)となっているのか不明です。

自分は unsigned long long を使っていたので型の違いを変更する前は、
10^N -9^N -9^Nまでの途中の内部的な計算結果のようなもの？が負数になっていることで、
unsigned long long で扱えない為結果がWAとなっていると推測しました。

そこで次のように計算順序を変更してみましたが結果は変わらずWAでした。
変更前：ll ans=powmod(10,n)-powmod(9,n)-powmod(9,n)+powmod(8,n);
変更後：ll ans=powmod(10,n)+powmod(8,n)-powmod(9,n)-powmod(9,n);

最後に型を全て long long に変更することでACとなりました。
unsigned long long の方がlong longよりも扱える数が大きいし途中計算でも負数になっていないはずです。
何故型の違いだけでWAになるのか理由が分かりません。

例えばN=2の時の手計算は、(10^2=100 - 9^2=81 - 9^2=81 + 8^2=64) = 2 の結果となります。
100-91-91 の時点で一時的に負数になるのは分かるのですが、

計算順序を変えると、(10^2=100 + 8^2=64- 9^2=81 - 9^2=81) = 2　当然同じ結果ですが、
途中計算では100 + 64 - 81 -81 と左から順に計算していれば負数になることはありません。

この部分以外で型が影響している箇所は無いと思ったのですが何かお気づきになりましたらご教示ください。

#追記：
※回答頂き途中計算を手計算したところ負数になっていました。
累乗計算の結果が負数にならないという思い込みから%MODの剰余で負数になることを想定出来なかったことが原因の実装ミスでした。
公式コードで long long を使っている理由がやっと理解出来ました。
ありがとうございました。

//公式で long longとなっている箇所全てを
typedef long long ll;

//自分は unsigned long long　としていた箇所を全てlong longにしたらACとなった。
using ull = unsigned long long;

// unsigned long long;
// in
// 1000000

// 907328795
// 803957911
// 961835147
// 961835147

// out
// 369960420

// using ll = long long;
// in
// 1000000

// 907328795
// 803957911
// 961835147
// 961835147

// out
// 787616419

###公式解説コード

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;
 
ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%mod;
    }
    return res;
}
int main(){
    ll n;
    cin>>n;
    ll ans=powmod(10,n)-powmod(9,n)-powmod(9,n)+powmod(8,n);
    ans%=mod;
    ans=(ans+mod)%mod;
    cout<<ans<<"\n";
}

2

2

開発環境

Win10 (10.0.18362)
VSC1.48.2
C++17
gcc version 10.2.0 (Rev1, Built by MSYS2 project)

Answer 1

powmodの返す値が、ただの累乗であれば、おっしゃっている通り、計算が途中で負になることはないでしょう。しかし実際に返しているのは、累乗の結果を1000000007で割ったあまりです。元の累乗の大小と累乗の余りの大小は、必ずしも一致しません。このため、計算結果自体が負になる可能性があります。

例えば、仮にpowmodが7の余りを返すとします。するとN=2のとき、元の累乗の計算は

100 + 64 - 81 - 81
= 2

ですが、7の余りで計算していくと

(100 mod 7) + (64 mod 7) - (81 mod 7) - (81 mod 7)
= 2 + 1 - 4 - 4
= -5

になります。

Comments

[mjk]

回答頂きありがとうございます。
ご指摘の通り問題の入力最大値を手計算するとpowmodの戻り値４つを合計するところで負数になっていました。
累乗計算の結果は負数にならないという思い込みでした。