結果
| 問題 | No.2151 3 on Torus-Lohkous |
| ユーザー |
 semiexp
|
| 提出日時 | 2022-12-09 23:47:16 |
| 言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
| 結果 |
CE
(最新)
AC
(最初)
|
| 実行時間 | - |
| コード長 | 5,930 bytes |
| コンパイル時間 | 3,762 ms |
| コンパイル使用メモリ | 113,792 KB |
| 最終ジャッジ日時 | 2024-04-27 04:21:33 |
| 合計ジャッジ時間 | 4,247 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp:24:31: error: no member named 'numeric_limits' in namespace 'std'
24 | static_assert(Mod <= std::numeric_limits<i32>::max());
| ~~~~~^
main.cpp:24:46: error: unexpected type name 'i32': expected expression
24 | static_assert(Mod <= std::numeric_limits<i32>::max());
| ^
main.cpp:24:50: error: no matching function for call to 'max'
24 | static_assert(Mod <= std::numeric_limits<i32>::max());
| ^~~~~
/usr/lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_algo.h:3461:5: note: candidate function template not viable: requires single argument '__l', but no arguments were provided
3461 | max(initializer_list<_Tp> __l)
| ^ ~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/algorithmfwd.h:407:5: note: candidate function template not viable: requires 2 arguments, but 0 were provided
407 | max(const _Tp&, const _Tp&);
| ^ ~~~~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/stl_algo.h:3467:5: note: candidate function template not viable: requires 2 arguments, but 0 were provided
3467 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/lib/gcc/x86_64-linux-gnu/11/../../../../include/c++/11/bits/algorithmfwd.h:412:5: note: candidate function template not viable: requires 3 arguments, but 0 were provided
412 | max(const _Tp&, const _Tp&, _Compare);
| ^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3 errors generated.
ソースコード
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
#define MOD 998244353
#define ADD(X,Y) ((X) = ((X) + (Y)%MOD) % MOD)
typedef long long i64; typedef vector<int> ivec; typedef vector<string> svec;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
template <u32 Mod> class ModInt {
using Self = ModInt<Mod>;
static_assert(Mod <= std::numeric_limits<i32>::max());
public:
ModInt(i64 value = 0) {
if (value < 0) {
value_ = (Mod - (-value % Mod)) % Mod;
} else {
value_ = value % Mod;
}
}
ModInt(const Self& other) : value_(other.value_) {}
operator i32() const {
return value_;
}
operator i64() const {
return value_;
}
Self operator+(const Self& other) const {
Self res(*this);
res += other;
return res;
}
Self operator-(const Self& other) const {
Self res(*this);
res -= other;
return res;
}
Self operator*(const Self& other) const {
Self res(*this);
res *= other;
return res;
}
Self operator/(const Self& other) const {
Self res(*this);
res /= other;
return res;
}
Self operator-() const {
Self res(0);
res -= *this;
return res;
}
Self pow(i64 power) const {
Self ret(1), p(*this);
if (power < 0) {
power *= -1;
p = p.inv();
}
for (i64 i = 0; (1 << i) <= power; ++i) {
if ((power >> i) & 1) ret *= p;
p *= p;
}
return ret;
}
Self& operator+=(const Self& other) {
value_ += other.value_;
if (value_ >= Mod) value_ -= Mod;
return *this;
}
Self& operator-=(const Self& other) {
value_ += Mod - other.value_;
if (value_ >= Mod) value_ -= Mod;
return *this;
}
Self& operator*=(const Self& other) {
value_ = (u32)(((u64)value_ * other.value_) % Mod);
return *this;
}
Self& operator/=(const Self& other) {
*this *= other.inv();
return *this;
}
Self inv() const {
if (value_ < inv_tbl_.size()) return inv_tbl_[value_];
if (Mod - value_ < inv_tbl_.size()) return Mod - inv_tbl_[Mod - value_];
else return pow(Mod - 2);
}
private:
u32 value_;
static const std::vector<Self> inv_tbl_;
};
template <u32 Mod>
std::vector<ModInt<Mod>> create_inv_tbl_(u32 n) {
std::vector<ModInt<Mod>> res;
res.reserve(n + 1);
res.push_back(0);
res.push_back(1);
for (u32 i = 2; i <= n; ++i) {
// MOD / i == 0
// MOD // i + (MOD % i) / i == 0
// 1 / i == -(MOD // i) / (MOD % i)
res.push_back(res[Mod % i] * ModInt<Mod>(Mod - (Mod / i)));
}
return res;
}
template <u32 Mod>
const std::vector<ModInt<Mod>> ModInt<Mod>::inv_tbl_ = create_inv_tbl_<Mod>(1000000);
template <class T, u32 Mod>
ModInt<Mod> operator+(T x, ModInt<Mod> y) {
return ModInt<Mod>(x) + y;
}
template <class T, u32 Mod>
ModInt<Mod> operator-(T x, ModInt<Mod> y) {
return ModInt<Mod>(x) - y;
}
template <class T, u32 Mod>
ModInt<Mod> operator*(T x, ModInt<Mod> y) {
return ModInt<Mod>(x) * y;
}
template <class T, u32 Mod>
ModInt<Mod> operator/(T x, ModInt<Mod> y) {
return ModInt<Mod>(x) / y;
}
template <class T, u32 Mod>
ModInt<Mod> operator+(ModInt<Mod> x, T y) {
return x + ModInt<Mod>(y);
}
template <class T, u32 Mod>
ModInt<Mod> operator-(ModInt<Mod> x, T y) {
return x - ModInt<Mod>(y);
}
template <class T, u32 Mod>
ModInt<Mod> operator*(ModInt<Mod> x, T y) {
return x * ModInt<Mod>(y);
}
template <class T, u32 Mod>
ModInt<Mod> operator/(ModInt<Mod> x, T y) {
return x / ModInt<Mod>(y);
}
typedef ModInt<MOD> mint;
int T;
int H, W;
mint fact[101010], facti[101010];
mint C(int x, int y) {
if (0 <= y && y <= x) {
return fact[x] * facti[x - y] * facti[y];
} else {
return 0;
}
}
int mygcd(int x, int y) {
while (y) {
int tmp = x % y;
x = y;
y = tmp;
}
return x;
}
mint solve(int H, int W) {
mint ans = 0;
ans += mint(H) * mint(W);
if (H % 4 == 0 && W % 4 == 0) {
ans += 16;
}
int g = mygcd(H, W);
if (g >= 4) {
ans += 2 * g;
}
if (g >= 5 && (H % 3 == 0 || W % 3 == 0)) {
ans += g * 12;
}
/*
if (g % 2 == 0) {
int g2 = g / 2;
mint tmp = 0;
for (int n5 = 1; n5 <= g2 / 5; ++n5) {
if ((g2 - 5 * n5) % 3 != 0) continue;
int n3 = (g2 - 5 * n5) / 3;
// printf("%d %d\n", n5, n3);
if (n5 >= 1) tmp += C(n5 - 1 + n3, n5 - 1) * 5;
if (n3 >= 1) tmp += C(n5 + n3 - 1, n3 - 1) * 3;
}
// printf("%d\n", (int)tmp);
ans += tmp * tmp * 4;
}
*/
if (g % 2 == 0) {
int g2 = g / 2;
mint tmp[2] = {0, 0};
for (int n5 = 1; n5 <= g2 / 5; ++n5) {
if ((g2 - 5 * n5) % 3 != 0) continue;
int n3 = (g2 - 5 * n5) / 3;
// printf("%d %d\n", n5, n3);
if (n5 >= 1) tmp[n5 % 2] += C(n5 - 1 + n3, n5 - 1) * 5;
if (n3 >= 1) tmp[n5 % 2] += C(n5 + n3 - 1, n3 - 1) * 3;
}
ans += tmp[0] * tmp[0] * 4;
ans += tmp[1] * tmp[1] * 4;
// printf("%d\n", (int)tmp);
}
return ans;
}
int main()
{
fact[0] = facti[0] = 1;
for (int i = 1; i < 101010; ++i) {
fact[i] = fact[i - 1] * i;
facti[i] = facti[i - 1] / i;
}
scanf("%d", &T);
for (;T--;) {
scanf("%d%d", &H, &W);
mint ans = solve(H, W);
printf("%d\n", (int)ans);
}
return 0;
}