結果

問題 No.2151 3 on Torus-Lohkous
コンテスト
ユーザー semiexp
提出日時 2022-12-09 23:47:16
言語 C++17(clang)
(17.0.6 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 5,930 bytes
コンパイル時間 4,040 ms
コンパイル使用メモリ 114,176 KB
最終ジャッジ日時 2024-11-15 03:01:52
合計ジャッジ時間 4,524 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、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.

ソースコード

diff #
raw source code 

#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;
}
0