#770136 (C++23) No.1973 Divisor Sequence

提出ソース

結果

問題	No.1973 Divisor Sequence
ユーザー	SnowBeenDiding
提出日時	2022-06-11 00:34:16
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	10 ms / 2,000 ms
コード長	8,176 bytes
コンパイル時間	5,756 ms
コンパイル使用メモリ	316,364 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-09-21 07:44:30
合計ジャッジ時間	6,318 ms
ジャッジサーバーID （参考情報）	judge5 / judge4

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	3 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	9 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	5 ms 6,940 KB
testcase_08	AC	3 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	2 ms 6,944 KB
testcase_12	AC	3 ms 6,940 KB
testcase_13	AC	2 ms 6,940 KB
testcase_14	AC	2 ms 6,944 KB
testcase_15	AC	2 ms 6,944 KB
testcase_16	AC	2 ms 6,940 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	2 ms 6,940 KB
testcase_20	AC	3 ms 6,944 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	10 ms 6,940 KB
testcase_24	AC	2 ms 6,940 KB

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

ソースコード

raw source code

#include <atcoder/all>
using namespace atcoder;
using mint = modint1000000007;
// using mint = modint998244353;
// using mint = modint;//mint::set_mod(MOD);

const long long MOD = 1000000007;
// const long long MOD = 998244353;

#include <bits/stdc++.h>
#define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
#define repeq(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); i++)
#define repreq(i, a, b) for (ll i = (ll)(a); i >= (ll)(b); i--)
#define each(a, b) for (auto &(a) : (b))
#define endl '\n'  // fflush(stdout);
#define cYes cout << "Yes" << endl
#define cNo cout << "No" << endl
#define sortr(v) sort(v, greater<>())
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define tget(a, b) get<b>(a)
#define FI first
#define SE second
#define ALL(v) (v).begin(), (v).end()
#define INFLL 3000000000000000100LL
#define INF 1000000100
#define PI acos(-1.0L)
#define TAU (PI * 2.0L)

using namespace std;

typedef long long ll;
typedef pair<ll, ll> Pll;
typedef tuple<ll, ll, ll> Tlll;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<ll> Vl;
typedef vector<Vl> VVl;
typedef vector<VVl> VVVl;
typedef vector<Tlll> VTlll;
typedef vector<mint> Vm;
typedef vector<Vm> VVm;
typedef vector<string> Vs;
typedef vector<double> Vd;
typedef vector<char> Vc;
typedef vector<bool> Vb;
typedef vector<Pll> VPll;
typedef priority_queue<ll> PQl;
typedef priority_queue<ll, vector<ll>, greater<ll>> PQlr;

/* print */
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &V) {
    int N = V.size();
    if (N == 0) {
        os << endl;
        return os;
    }
    rep(i, 0, N - 1) { os << V[i] << ' '; }
    os << V[N - 1] << endl;
    return os;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<vector<T>> &V) {
    int N = V.size();
    rep(i, 0, N) os << V[i];
    return os;
}
template <typename T, typename S>
ostream &operator<<(ostream &os, pair<T, S> const &P) {
    os << P.FI << ' ' << P.SE;
    return os;
}
ostream &operator<<(ostream &os, mint const &M) {
    os << M.val();
    return os;
}

/* useful */
template <typename T>
void Vin(vector<T> &v) {
    int n = v.size();
    rep(i, 0, n) cin >> v[i];
}
template <typename T>
int SMALLER(vector<T> &a, T x) {
    return lower_bound(a.begin(), a.end(), x) - a.begin();
}
template <typename T>
int orSMALLER(vector<T> &a, T x) {
    return upper_bound(a.begin(), a.end(), x) - a.begin();
}
template <typename T>
int BIGGER(vector<T> &a, T x) {
    return a.size() - orSMALLER(a, x);
}
template <typename T>
int orBIGGER(vector<T> &a, T x) {
    return a.size() - SMALLER(a, x);
}
template <typename T>
int COUNT(vector<T> &a, T x) {
    return upper_bound(ALL(a), x) - lower_bound(ALL(a), x);
}
template <typename T>
bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
void press(T &v) {
    v.erase(unique(ALL(v)), v.end());
}
template <typename T>
vector<int> zip(vector<T> b) {
    pair<T, int> p[b.size() + 10];
    int a = b.size();
    vector<int> l(a);
    for (int i = 0; i < a; i++) p[i] = mp(b[i], i);
    sort(p, p + a);
    int w = 0;
    for (int i = 0; i < a; i++) {
        if (i && p[i].first != p[i - 1].first) w++;
        l[p[i].second] = w;
    }
    return l;
}
template <typename T>
vector<T> vis(vector<T> &v) {
    vector<T> S(v.size() + 1);
    rep(i, 1, S.size()) S[i] += v[i - 1] + S[i - 1];
    return S;
}

ll dem(ll a, ll b) { return ((a + b - 1) / (b)); }
ll dtoll(double d, int g) { return round(d * pow(10, g)); }

const double EPS = 1e-10;

void init() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(12);
}

// Comm + K -> Comm + 0
// Comm + K -> Comm + C = add//
// Comm + K -> Comm + U = del//

/********************************** START **********************************/

template <class T>
struct Matrix {
    vector<vector<T>> A;

    Matrix() {}

    Matrix(size_t n, size_t m) : A(n, vector<T>(m, 0)) {}

    Matrix(size_t n) : A(n, vector<T>(n, 0)){};

    size_t height() const { return (A.size()); }

    size_t width() const { return (A[0].size()); }

    inline const vector<T> &operator[](int k) const { return (A.at(k)); }

    inline vector<T> &operator[](int k) { return (A.at(k)); }

    static Matrix I(size_t n) {
        Matrix mat(n);
        for (int i = 0; i < n; i++) mat[i][i] = 1;
        return (mat);
    }

    Matrix &operator+=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) (*this)[i][j] += B[i][j];
        return (*this);
    }

    Matrix &operator-=(const Matrix &B) {
        size_t n = height(), m = width();
        assert(n == B.height() && m == B.width());
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) (*this)[i][j] -= B[i][j];
        return (*this);
    }

    Matrix &operator*=(const Matrix &B) {
        size_t n = height(), m = B.width(), p = width();
        assert(p == B.height());
        vector<vector<T>> C(n, vector<T>(m, 0));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < p; k++)
                    C[i][j] = (C[i][j] + (*this)[i][k] * B[k][j]);
        A.swap(C);
        return (*this);
    }

    Matrix &operator^=(long long k) {
        Matrix B = Matrix::I(height());
        while (k > 0) {
            if (k & 1) B *= *this;
            *this *= *this;
            k >>= 1LL;
        }
        A.swap(B.A);
        return (*this);
    }

    Matrix operator+(const Matrix &B) const { return (Matrix(*this) += B); }

    Matrix operator-(const Matrix &B) const { return (Matrix(*this) -= B); }

    Matrix operator*(const Matrix &B) const { return (Matrix(*this) *= B); }

    Matrix operator^(const long long k) const { return (Matrix(*this) ^= k); }

    friend ostream &operator<<(ostream &os, Matrix &p) {
        size_t n = p.height(), m = p.width();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                os << p[i][j] << (j + 1 == m ? "\n" : " ");
            }
        }
        return (os);
    }

    T determinant() {  // O(n^3)
        Matrix B(*this);
        assert(width() == height());
        T ret = 1;
        for (int i = 0; i < width(); i++) {
            int idx = -1;
            for (int j = i; j < width(); j++) {
                if (B[j][i] != 0) idx = j;
            }
            if (idx == -1) return (0);
            if (i != idx) {
                ret *= -1;
                swap(B[i], B[idx]);
            }
            ret *= B[i][i];
            T vv = B[i][i];
            for (int j = 0; j < width(); j++) {
                B[i][j] /= vv;
            }
            for (int j = i + 1; j < width(); j++) {
                T a = B[j][i];
                for (int k = 0; k < width(); k++) {
                    B[j][k] -= B[i][k] * a;
                }
            }
        }
        return (ret);
    }
};

vector<pair<long long, long long>> fact(long long n) {  // 素因数分解O(√N)
    vector<pair<long long, long long>> r;
    for (ll i = 2; i * i <= n; ++i) {
        if (n % i) continue;
        r.emplace_back(i, 0);
        while (n % i == 0) {
            n /= i;
            r.back().second++;
        }
    }
    if (n != 1) r.emplace_back(n, 1);
    return r;
}

void sol() {
    ll n, m;
    cin >> n >> m;
    auto v = fact(m);
    mint ans = 1;
    auto f = [&](ll k) {
        Vm v(k + 1, 1);
        Matrix<mint> m(k + 1);
        rep(i, 0, k + 1) {
            repreq(j, k, k - i) { m[i][j] = 1; }
        }
        m ^= n - 1;
        mint ret = 0;
        rep(i, 0, k + 1) {
            mint ad = 0;
            rep(j, 0, k + 1) { ad += m[i][j] * v[j]; }
            ret += ad;
        }
        return ret;
    };
    rep(i, 0, v.size()) { ans *= f(v[i].SE); }
    cout << ans << endl;
}

int main() {
    init();
    int q = 1;
    // cin >> q;
    while (q--) sol();
    return 0;
}

yukicoder

結果

テストケース

ソースコード