結果

問題 No.1050 Zero (Maximum)
ユーザー yoshnaryyoshnary
提出日時 2020-05-09 04:38:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 19 ms / 2,000 ms
コード長 4,099 bytes
コンパイル時間 804 ms
コンパイル使用メモリ 75,776 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-04 15:30:50
合計ジャッジ時間 1,605 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 6 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 13 ms
5,376 KB
testcase_05 AC 13 ms
5,376 KB
testcase_06 AC 6 ms
5,376 KB
testcase_07 AC 7 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 4 ms
5,376 KB
testcase_10 AC 15 ms
5,376 KB
testcase_11 AC 11 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 16 ms
5,376 KB
testcase_17 AC 19 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cassert>

// Modint
struct Mint {
    static const long long mod = (long long)1e9 + 7;
    long long val;

    Mint() { val = 0; }
    Mint(long long a) { val = a; verify_value(); }

    void verify_value() {
        if (val >= mod) val %= mod;
        if (val < 0) val %= mod, val += mod;
    }

    Mint pow(long long p) const {
        Mint cur = Mint(val), ret = 1;
        while (p > 0) {
            if (p & 1) ret *= cur;
            cur *= cur;
            p >>= 1LL;
        }
        return ret;
    }
    Mint inv() const {
        if (val == 0)
            std::cerr << "WARNING: inv() is called with 0." << std::endl;
        return pow(mod - 2);
    }

    Mint operator+() const { return *this; }
    Mint operator-() const { return Mint(mod - val); }

    Mint operator+=(const Mint &a) {
        val += a.val;
        if (val >= mod) val -= mod;
        return Mint(val);
    }
    Mint operator*=(const Mint &a) {
        val *= a.val;
        if (val >= mod) val %= mod;
        return Mint(val);
    }
    Mint operator-=(const Mint &a) { return *this += -a; }
    Mint operator/=(const Mint &a) { return *this *= a.inv(); }

    Mint operator++() { return *this += Mint(1); }
    Mint operator--() { return *this -= Mint(1); }
    Mint operator++(int) {
        Mint ret = *this;
        ++(*this);
        return ret;
    }
    Mint operator--(int) {
        Mint ret = *this;
        --(*this);
        return ret;
    }

    operator long long() const { return val; }
};

Mint operator+(const Mint &a, const Mint &b) {
    long long ret = a.val + b.val;
    if (ret >= Mint::mod) ret -= Mint::mod;
    return Mint(ret);
}
Mint operator*(const Mint &a, const Mint &b) {
    long long ret = a.val * b.val;
    if (ret >= Mint::mod) ret %= Mint::mod;
    return Mint(ret);
}
Mint operator-(const Mint &a, const Mint &b) { return a + (-b); }
Mint operator/(const Mint &a, const Mint &b) { return a * b.inv(); }

std::ostream &operator<<(std::ostream &out, const Mint &a) { return out << a.val; }
std::istream &operator>>(std::istream &in, Mint &a) {
    in >> a.val;
    a.verify_value();
    return in;
}

Mint pow(Mint a, long long b) {
    return a.pow(b);
}

// Matrix power
template<typename T>
class Matrix {
public:
    Matrix(int n, int m) : dat(n, std::vector<T>(m)) {}
    Matrix(int n, int m, T init_val) : dat(n, std::vector<T>(m, init_val)) {}
    Matrix(int n) : Matrix(n, n) {}
    Matrix(int n, T init_val) : Matrix(n, n, init_val) {}
    std::vector<T> &operator[](size_t idx) { return dat[idx]; }
    const std::vector<T> &operator[](size_t idx) const { return dat[idx]; }
    size_t size() const { return dat.size(); }

private:
    std::vector<std::vector<T>> dat;
};
template<typename T>
std::ostream &operator<<(std::ostream &out, const Matrix<T> &a) {
    for (int i = 0; i < (int)a.size(); i++) {
        for (int j = 0; j < (int)a[i].size(); j++) {
            out << a[i][j] << " \n"[j == (int)a[i].size() - 1];
        }
    }
    return out;
}

template<typename T>
Matrix<T> matmul(const Matrix<T> &a, const Matrix<T> &b) {
    int n = (int)a.size();
    int m = (int)b[0].size();
    int r = (int)b.size();
    assert(a[0].size() == r);
    Matrix<T> ret(n, m);
    for (int i = 0; i < n; i++) {
        for (int k = 0; k < r; k++) {
            for (int j = 0; j < m; j++) {
                ret[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return ret;
}

template<typename T>
Matrix<T> matpow(Matrix<T> a, long long p) {
    int n = (int)a.size();
    Matrix<T> ret(n);
    for (int i = 0; i < n; i++) ret[i][i] = 1;
    while (p > 0) {
        if (p & 1) ret = matmul(ret, a);
        a = matmul(a, a);
        p >>= 1LL;
    }
    return ret;
}

int main() {
    int m, k; std::cin >> m >> k;
    Matrix<Mint> mat(m), v(m, 1);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            mat[(j + i) % m][j]++;
            mat[(j * i) % m][j]++;
        }
    }
    v[0][0] = 1;
    std::cout << matmul(matpow(mat, k), v)[0][0] << std::endl;
    return 0;
}
0