#598541 (C++17) No.886 Direct

提出ソース

結果

問題	No.886 Direct
ユーザー	Pachicobue
提出日時	2020-12-31 05:06:12
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	265 ms / 4,000 ms
コード長	10,514 bytes
コンパイル時間	2,583 ms
コンパイル使用メモリ	211,384 KB
実行使用メモリ	75,436 KB
最終ジャッジ日時	2024-10-08 19:44:05
合計ジャッジ時間	5,522 ms
ジャッジサーバーID （参考情報）	judge2 / judge3

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,248 KB
testcase_02	AC	2 ms 5,248 KB
testcase_03	AC	2 ms 5,248 KB
testcase_04	AC	2 ms 5,248 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	1 ms 5,248 KB
testcase_07	AC	2 ms 5,248 KB
testcase_08	AC	2 ms 5,248 KB
testcase_09	AC	2 ms 5,248 KB
testcase_10	AC	2 ms 5,248 KB
testcase_11	AC	2 ms 5,248 KB
testcase_12	AC	2 ms 5,248 KB
testcase_13	AC	3 ms 5,248 KB
testcase_14	AC	2 ms 5,248 KB
testcase_15	AC	2 ms 5,248 KB
testcase_16	AC	2 ms 5,248 KB
testcase_17	AC	3 ms 5,248 KB
testcase_18	AC	3 ms 5,248 KB
testcase_19	AC	3 ms 5,248 KB
testcase_20	AC	3 ms 5,248 KB
testcase_21	AC	3 ms 5,248 KB
testcase_22	AC	3 ms 5,248 KB
testcase_23	AC	56 ms 22,016 KB
testcase_24	AC	84 ms 31,756 KB
testcase_25	AC	42 ms 18,200 KB
testcase_26	AC	46 ms 19,784 KB
testcase_27	AC	170 ms 52,312 KB
testcase_28	AC	160 ms 52,512 KB
testcase_29	AC	88 ms 39,632 KB
testcase_30	AC	85 ms 39,632 KB
testcase_31	AC	251 ms 75,424 KB
testcase_32	AC	243 ms 75,344 KB
testcase_33	AC	249 ms 75,436 KB
testcase_34	AC	265 ms 75,344 KB
testcase_35	AC	259 ms 75,308 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <bits/stdc++.h>
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using f64 = double;
using f80 = long double;
using f128 = __float128;
using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using LL = __int128_t;
using ULL = __uint128_t;
template<typename T> using max_heap = std::priority_queue<T>;
template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
std::vector<int> factor_table(const int sup)
{
    std::vector<int> fact(sup);
    std::iota(fact.begin(), fact.end(), 0);
    for (int i = 2; i < sup; i++) {
        if (fact[i] != i) { continue; }
        for (int j = i + i; j < sup; j += i) { fact[j] = i; }
    }
    return fact;
}
std::vector<i32> prime_enumerate(const i32 sup)
{
    const auto ftable = factor_table(sup);
    std::vector<i32> ps;
    for (i32 p = 2; p < sup; p++) {
        if (ftable[p] == p) { ps.push_back(p); }
    }
    return ps;
}
template<typename T>
std::vector<T> divisors_moebius(const std::vector<T>& xs, const bool subset)
{
    const int N = (int)xs.size();
    auto ys = xs;
    for (const i32 p : prime_enumerate(N)) {
        if (subset) {
            for (i32 i = (N - 1) / p; i >= 1; i--) { ys[i * p] -= ys[i]; }
        } else {
            for (i32 i = 1; i * p < N; i++) { ys[i] -= ys[i * p]; }
        }
    }
    return ys;
}
template<typename T>
std::vector<T> divisors_zeta(const std::vector<T>& xs, const bool subset)
{
    const int N = (int)xs.size();
    auto ys = xs;
    for (const i32 p : prime_enumerate(N)) {
        if (subset) {
            for (i32 i = 1; i * p < N; i++) { ys[i * p] += ys[i]; }
        } else {
            for (i32 i = (N - 1) / p; i >= 1; i--) { ys[i] += ys[i * p]; }
        }
    }
    return ys;
}
template<typename T>
std::vector<T> gcd_convolute(const std::vector<T>& f, const std::vector<T>& g)
{
    const int N = (int)std::min(f.size(), g.size());
    auto F = divisors_zeta(f, false), G = divisors_zeta(g, false);
    F.resize(N), G.resize(N);
    for (int i = 0; i < N; i++) { F[i] *= G[i]; }
    return divisors_moebius(F, false);
}
struct modinfo
{
    void set_mod(const uint nmod) { mod = nmod; }
    uint mod, root, max2p;
};
template<const modinfo& info>
class modint
{
public:
    static constexpr const uint& mod = info.mod;
    static constexpr const uint& root = info.root;
    static constexpr const uint& max2p = info.max2p;
    constexpr modint() : m_val{0} {}
    constexpr modint(const ll v) : m_val{normll(v)} {}
    constexpr void set_raw(const uint v) { m_val = v; }
    constexpr modint operator-() const { return modint{0} - (*this); }
    constexpr modint& operator+=(const modint& m) { return m_val = norm(m_val + m()), *this; }
    constexpr modint& operator-=(const modint& m) { return m_val = norm(m_val + mod - m()), *this; }
    constexpr modint& operator*=(const modint& m) { return m_val = normll((ll)m_val * (ll)m() % (ll)mod), *this; }
    constexpr modint& operator/=(const modint& m) { return *this *= m.inv(); }
    constexpr modint operator+(const modint& m) const { return modint{*this} += m; }
    constexpr modint operator-(const modint& m) const { return modint{*this} -= m; }
    constexpr modint operator*(const modint& m) const { return modint{*this} *= m; }
    constexpr modint operator/(const modint& m) const { return modint{*this} /= m; }
    constexpr bool operator==(const modint& m) const { return m_val == m(); }
    constexpr bool operator!=(const modint& m) const { return not(*this == m); }
    friend std::istream& operator>>(std::istream& is, modint& m)
    {
        ll v;
        return is >> v, m = v, is;
    }
    friend std::ostream& operator<<(std::ostream& os, const modint& m) { return os << m(); }
    constexpr uint get() const { return m_val; }
    constexpr uint operator()() const { return m_val; }
    constexpr modint pow(ull n) const
    {
        modint ans = 1;
        for (modint x = *this; n > 0; n >>= 1, x *= x) {
            if (n & 1ULL) { ans *= x; }
        }
        return ans;
    }
    constexpr modint inv() const { return pow(mod - 2); }
    static modint sinv(const uint n)
    {
        static std::vector<modint> is{1, 1};
        for (uint i = (uint)is.size(); i <= n; i++) { is.push_back(-is[mod % i] * (mod / i)); }
        return is[n];
    }
    static modint fact(const uint n)
    {
        static std::vector<modint> fs{1, 1};
        for (uint i = (uint)fs.size(); i <= n; i++) { fs.push_back(fs.back() * i); }
        return fs[n];
    }
    static modint ifact(const uint n)
    {
        static std::vector<modint> ifs{1, 1};
        for (uint i = (uint)ifs.size(); i <= n; i++) { ifs.push_back(ifs.back() * sinv(i)); }
        return ifs[n];
    }
    static modint comb(const int n, const int k) { return k > n or k < 0 ? modint{0} : fact(n) * ifact(n - k) * ifact(k); }
private:
    static constexpr uint norm(const uint x) { return x < mod ? x : x - mod; }
    static constexpr uint normll(const ll x) { return norm(uint(x % (ll)mod + (ll)mod)); }
    uint m_val;
};
constexpr modinfo modinfo_1000000007 = {1000000007, 5, 1};
constexpr modinfo modinfo_998244353 = {998244353, 3, 23};
using modint_1000000007 = modint<modinfo_1000000007>;
using modint_998244353 = modint<modinfo_998244353>;
class printer
{
public:
    printer()
    {
        for (int i = 0; i < 10000; i++) {
            for (int j = i, t = 3; t >= 0; t--, j /= 10) { m_dict[i * 4 + t] = (j % 10) + '0'; }
        }
    }
    ~printer() { flush(); }
    template<typename... Args> int ln(const Args&... args) { return dump(args...), put_char('\n'), 0; }
    template<typename... Args> int el(const Args&... args) { return dump(args...), put_char('\n'), flush(), 0; }
private:
    using ll = long long;
    using ull = unsigned long long;
    static constexpr ull TEN(const int d) { return d == 0 ? 1ULL : TEN(d - 1) * 10ULL; }
    void flush() { fwrite(m_memory, 1, m_tail, stdout), m_tail = 0; }
    void put_char(const char c) { m_memory[m_tail++] = c; }
    static constexpr int dn(const ull x)
    {
        return x < TEN(10)
                   ? x < TEN(5)
                         ? x < TEN(2)
                               ? x < TEN(1) ? 1 : 2
                               : x < TEN(3) ? 3 : x < TEN(4) ? 4 : 5
                         : x < TEN(7)
                               ? x < TEN(6) ? 6 : 7
                               : x < TEN(8) ? 8 : x < TEN(9) ? 9 : 10
                   : x < TEN(14)
                         ? x < TEN(12)
                               ? x < TEN(11) ? 11 : 12
                               : x < TEN(13) ? 13 : 14
                         : x < TEN(16)
                               ? x < TEN(15) ? 15 : 16
                               : x < TEN(17) ? 17 : x < TEN(18) ? 18 : 19;
    }
    void dump(const char* s) { dump(std::string{s}); }
    void dump(const std::string& s)
    {
        for (const char c : s) { put_char(c); }
    }
    template<typename T>
    void dump(T v)
    {
        if (C - m_tail < 50) { flush(); }
        if (v < 0) { put_char('-'), v = -v; }
        const auto d = dn(v);
        int i = d - 4;
        for (i = d - 4; i >= 0; i -= 4, v /= 10000) { memcpy(m_memory + m_tail + i, m_dict + (v % 10000) * 4, 4); }
        memcpy(m_memory + m_tail, m_dict + v * 4 - i, i + 4);
        m_tail += d;
    }
    template<typename T>
    void dump(const std::vector<T>& vs)
    {
        for (int i = 0; i < (int)vs.size(); i++) {
            if (i > 0) { put_char(' '); }
            dump(vs[i]);
        }
    }
    template<typename T>
    void dump(const std::vector<std::vector<T>>& vss)
    {
        for (int i = 0; i < (int)vss.size(); i++) {
            if (i > 0) { put_char('\n'); }
            dump(vss[i]);
        }
    }
    template<typename T, typename... Args> void dump(const T& v, const Args&... args) { return dump(v), put_char(' '), dump(args...), void(0); }
    static constexpr int C = 1 << 18;
    int m_tail = 0;
    char m_memory[C];
    char m_dict[10000 * 4];
} out;
class scanner
{
public:
    scanner() {}
    template<typename T>
    T val()
    {
        if (m_tail - m_head < 40) { disk_read(); }
        char c = get_char();
        const bool neg = (c == '-');
        if (neg) { c = get_char(); }
        T ans = 0;
        while (c >= '0') {
            ans = ans * T{10} + (c - '0');
            c = get_char();
        }
        return (neg ? -ans : ans);
    }
    template<typename T> T val(const T offset) { return val<T>() - offset; }
    template<typename T> std::vector<T> vec(const int n)
    {
        return make_v<T>(n, [this]() { return val<T>(); });
    }
    template<typename T> std::vector<T> vec(const int n, const T offset)
    {
        return make_v<T>(n, [this, offset]() { return val<T>(offset); });
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1)
    {
        return make_v<std::vector<T>>(n0, [this, n1]() { return vec<T>(n1); });
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset)
    {
        return make_v<std::vector<T>>(n0, [this, n1, offset]() { return vec<T>(n1, offset); });
    }
    template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; }
    template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; }
private:
    template<typename T, typename F>
    std::vector<T> make_v(const int n, F f)
    {
        std::vector<T> ans;
        for (int i = 0; i < n; i++) { ans.push_back(f()); }
        return ans;
    }
    char get_char() { return m_memory[m_head++]; }
    void disk_read()
    {
        std::copy(m_memory + m_head, m_memory + m_tail, m_memory);
        m_tail -= m_head, m_head = 0;
        m_tail += fread(m_memory + m_tail, 1, C - m_tail, stdin);
    }
    static constexpr int C = 1 << 18;
    int m_head = 0, m_tail = 0;
    char m_memory[C];
} in;
int main()
{
    using mint = modint_1000000007;
    const auto [H, W] = in.tup<int, int>();
    mint ans = mint(H) * (W - 1) + mint(H - 1) * W;
    std::vector<mint> as(H), bs(W);
    for (int i = 1; i < H; i++) { as[i] = H - i; }
    for (int i = 1; i < W; i++) { bs[i] = W - i; }
    const auto cs = gcd_convolute(as, bs);
    ans += (cs.size() < 2 ? mint{0} : cs[1]) * 2;
    out.ln(ans());
    return 0;
}

yukicoder

結果

テストケース

ソースコード