結果

問題 No.1105 Many Triplets
コンテスト
ユーザー TAISA_
提出日時 2020-06-02 23:50:25
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 2,890 bytes
コンパイル時間 2,274 ms
コンパイル使用メモリ 193,368 KB
最終ジャッジ日時 2025-01-10 20:41:48
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000000007LL; //from http://noshi91.hatenablog.com/entry/2019/03/31/174006
template <std::uint_fast64_t Modulus>
class modint {
    using u64 = std::uint_fast64_t;

  public:
    u64 a;
    constexpr modint(const u64 x = 0) noexcept : a(x % Modulus) {}
    constexpr u64 &value() noexcept { return a; }
    constexpr const u64 &value() const noexcept { return a; }
    constexpr modint operator+(const modint rhs) const noexcept {
        return modint(*this) += rhs;
    }
    constexpr modint operator-(const modint rhs) const noexcept {
        return modint(*this) -= rhs;
    }
    constexpr modint operator*(const modint rhs) const noexcept {
        return modint(*this) *= rhs;
    }
    constexpr modint operator/(const modint rhs) const noexcept {
        return modint(*this) /= rhs;
    }
    constexpr modint operator^(const u64 rhs) const noexcept {
        return modint(*this) ^= rhs;
    }
    constexpr modint &operator+=(const modint rhs) noexcept {
        a += rhs.a;
        if (a >= Modulus) {
            a -= Modulus;
        }
        return *this;
    }
    constexpr modint &operator-=(const modint rhs) noexcept {
        if (a < rhs.a) {
            a += Modulus;
        }
        a -= rhs.a;
        return *this;
    }
    constexpr modint &operator*=(const modint rhs) noexcept {
        a = a * rhs.a % Modulus;
        return *this;
    }
    constexpr modint &operator/=(modint rhs) noexcept {
        u64 exp = Modulus - 2;
        while (exp) {
            if (exp % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
    constexpr modint &operator^=(u64 exp) {
        modint rhs = modint(*this);
        a = 1;
        while (exp) {
            if (exp % 2) {
                *this *= rhs;
            }
            rhs *= rhs;
            exp /= 2;
        }
        return *this;
    }
    friend ostream &operator<<(ostream &os, const modint &x) {
        os << x.a;
        return os;
    }
    friend istream &operator>>(istream &is, modint &x) {
        is >> x.a;
        return is;
    }
};
using mint = modint<MOD>;
int main() {
    ll n;
    mint a, b, c;
    cin >> n >> a >> b >> c;
    assert(2<=n&&n<=1000000000000000000LL);
    assert(0<=a.a&&a.a<=1e9);
    assert(0<=b.a&&b.a<=1e9);
    assert(0<=c.a&&c.a<=1e9);
    auto act = [&] {
        mint na = a - b, nb = b - c, nc = c - a;
        a = na, b = nb, c = nc;
    };
    act();
    n -= 2LL;
    int f = n % 2LL;
    n /= 2LL;
    if (n % 3 > 0) {
        swap(a, c);
        swap(a, b);
        if (n % 3 > 1) {
            swap(a, c);
            swap(a, b);
        }
    }
    mint s = mint(MOD - 3LL) ^ n;
    a *= s;
    b *= s;
    c *= s;
    if (f) act();
    cout << a << " " << b << " " << c << endl;
}
0