Official

B - ABC-DEF Editorial by mechanicalpenciI


基本的には, 問題文の指示通り, \((A*B*C-D*E*F)\%998244353\) の値を求めれば良いです。 ここで、気をつけなければならない点はオーバーフローについてです。c++等の言語の整数型変数では, 扱える範囲が決まっており, その範囲を超えた数値を扱おうとすると, 想定外の挙動をする事があります。 \(64\) bit符号付き整数型では, \(2^{63}-1=9,223,372,036,854,775,807\simeq 9\times 10^{18}\) 程度までしか扱えないため, 今回のような計算においては途中でその値を超えないように計算を行う必要があります。

一般に非負整数 \(A,B\) および正整数 \(M\) について、 \((A*B)\%M=((A\%M)*(B\%M))\%M\)が成り立つ事に注意すれば, 計算前に各変数について, \(998244353\) で割ったあまりを求めた後に積を取れば良いと分かります。

また、先に余りを取っているので最後に差分を取る時, 負の値になり得ることに注意してください。この場合は\(998244353\)を足すことで正しい答を得る事ができます。

c++ による実装例 :

#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;

int main() {
  long long a,b,c,d,e,f;
  long long x,y,ans;

  cin >> a >> b >> c >> d >> e >> f;

  x=((a%mod)*(b%mod))%mod;
  x=(x*(c%mod))%mod;
  y=((d%mod)*(e%mod))%mod;
  y=(y*(f%mod))%mod;

  ans=(x+mod-y)%mod;

  cout << ans <<endl;
  return 0;
}

Python の場合はオーバーフローは起きません。 ただし、桁数に従って計算時間は増加していくため、そういった事が問題になる場合には注意が必要です。

Python による実装例 :

a,b,c,d,e,f=map(int, input().split())
print((a*b*c-d*e*f)%998244353)

posted:
last update: