結果

問題 No.1973 Divisor Sequence
コンテスト
ユーザー moharan627
提出日時 2022-06-10 22:19:00
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,361 bytes
コンパイル時間 5,975 ms
コンパイル使用メモリ 332,088 KB
実行使用メモリ 131,588 KB
最終ジャッジ日時 2024-09-21 06:29:23
合計ジャッジ時間 14,063 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 11 TLE * 1 -- * 10
権限があれば一括ダウンロードができます

ソースコード

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]; }
};
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 Move;
    rep(j,D){
        rep(k,D){
            if(Dflag[div[j]*div[k]]==1){
                Move.push_back({j,k});
            }
        }
    }
    range(i,1,N){
        for(auto jk:Move){
            DP[i+1][jk[1]] += DP[i][jk[0]];
        }
    }
    mint1 ans = 0;
    rep(d,D)ans += DP[N][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