結果

問題 No.1973 Divisor Sequence
コンテスト
ユーザー moharan627
提出日時 2022-06-10 22:38:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
(最新)
AC  
(最初)
実行時間 -
コード長 4,097 bytes
コンパイル時間 5,923 ms
コンパイル使用メモリ 332,680 KB
実行使用メモリ 814,720 KB
最終ジャッジ日時 2024-09-21 07:30:58
合計ジャッジ時間 10,578 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21 MLE * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#if !__INCLUDE_LEVEL__

#include __FILE__
vector<ll> lldiv(ll n) { 
    vector<ll> S;
    for (ll i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { S.push_back(i); if (i*i != n) S.push_back(n / i); }
    sort(S.begin(), S.end());
    return S;
}
template <typename T>
struct Compress {
    vector<T> xs;

    Compress() = default;

    Compress(const vector<T> &vs) { add(vs); }

    Compress(const initializer_list<vector<T>> &vs) {
        for (auto &p : vs) add(p);
    }

    void add(const vector<T> &vs) {
        copy(begin(vs), end(vs), back_inserter(xs));
    }

    void add(const T &x) { xs.emplace_back(x); }

    void build() {
        sort(begin(xs), end(xs));
        xs.erase(unique(begin(xs), end(xs)), end(xs));
    }

    vector<int> get(const vector<T> &vs) const {
        vector<int> ret;
        transform(begin(vs), end(vs), back_inserter(ret), [&](const T &x) {
            return lower_bound(begin(xs), end(xs), x) - begin(xs);
        });
        return ret;
    }

    int get(const T &x) const {
        return lower_bound(begin(xs), end(xs), x) - begin(xs);
    }

    const T &operator[](int k) const { return xs[k]; }
};
//行列の積
#define mat vector<vector<ll>>
const ll MOD = 1000000007;
mat mat_mul(mat &a, mat &b) {
    mat res(a.size(), vector<ll>(b[0].size()));
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b[0].size(); j++) {
            for (int k = 0; k < b.size(); k++) {
                (res[i][j] += a[i][k] * b[k][j]) %= MOD;
            }
        }
    }
    return res;
}
/// 行列累乗
mat mat_pow(mat a, long long n) {
    mat res(a.size(), vector<ll>(a.size()));
    // 単位行列で初期化
    for (int i = 0; i < a.size(); i++)res[i][i] = 1;
    // 繰り返し二乗法
    while (n > 0) {
        if (n & 1) res = mat_mul(a, res);
        a = mat_mul(a, a);
        n >>= 1;
        }
    return res;
}
int main()
{
    ll N,M;cin >> N >> M;
    auto div = lldiv(M);
    Compress<ll> comp(div);
    comp.build();
    ll D = div.size();
    vector<vector<mint1>> DP(N+1,vector<mint1>(D,0));
    unordered_map<ll,int> Dflag;
    fore(d,div){
        Dflag[d] = 1;
        DP[1][comp.get(d)] = 1;
    }
    vvl Mat(D,vl(D,0));
    rep(j,D){
        rep(k,D){
            if(Dflag[div[j]*div[k]]==1){
                Mat[j][k] = 1;
            }
        }
    }
    mat R = mat_pow(Mat,N-1);
    mat L(1,vl(D,1));
    mat Ans(1,vl(N,0));
    Ans = mat_mul(L,R);
    mint1 ans = 0;
    rep(d,D)ans += Ans[0][d];
    cout << ans << endl;
}

#else

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define range(i, m, n) for(int i = m; i < n; i++)
#define fore(i,a) for(auto &i:a)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define Sum(v) accumulate(all(v),0)
#define minv(v) *min_element(all(v))
#define maxv(v) *max_element(all(v))
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
const ll INF = 1e16;
const ll MOD1 = 1000000007;
const ll MOD2 = 998244353;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
ll SN(char s){return ll(s-'0');}
ll SN(string s){return stoll(s);}
int alpN(char s){return int(s-'a');}
int AlpN(char s){return int(s-'A');}
using Graph = vector<vector<ll>>;
using GraphCost = vector<vector<pair<ll,ll>>>;
using mint1 = modint1000000007;
using mint2 = modint998244353;
using pll = pair<long long, long long>;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v){for(int i=0;i<(int)v.size();i++)o<<(i>0?" ":"")<<v[i];return o;}//vector空白区切り出力
ostream& operator<<(ostream& os, const mint1& N) {return os << N.val();}//mint出力。デフォはmint1
ostream& operator<<(ostream& os, const mint2& N) {return os << N.val();}
template<class T> bool contain(const std::string& s, const T& v) {
    return s.find(v) != std::string::npos;
}

#endif
0