結果
問題 | No.1581 Multiple Sequence |
ユーザー |
![]() |
提出日時 | 2023-09-09 01:15:27 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 276 ms / 2,000 ms |
コード長 | 3,266 bytes |
コンパイル時間 | 2,070 ms |
コンパイル使用メモリ | 200,204 KB |
最終ジャッジ日時 | 2025-02-16 20:35:35 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define rep(i,n) for (int i = 0; i < (int)(n); ++i)#define Rep(i,a,b) for (int i = a; i < b; ++i)#define rRep(i,a,b) for (int i = a; i > b; --i)#define fore(i,a) for(auto &i:a)#define all(v) (v).begin(),(v).end()#define rall(v) (v).rbegin(),(v).rend()#define Unique(v) v.erase(unique(v.begin(), v.end()), v.end());#define Bit(x,i) (((x)>>(i))&1)#define fi first#define se secondusing ll = long long;using vi = vector<int>;using vll = vector<long long>;using vvi = vector<vi>;using vvll = vector<vll>;using pii = pair<int, int>;using pll = pair<ll, ll>;template<class T, size_t n, size_t idx = 0> auto mvec(const size_t (&d)[n], const T& init) noexcept { if constexpr (idx < n) return std::vector(d[idx], mvec<T, n, idx + 1>(d, init)); else return init; }template<class T, size_t n> auto mvec(const size_t (&d)[n]) noexcept { return mvec(d, T{}); }void print(){ cout << '\n'; }template<class T, class... Ts> void print(const T& a, const Ts&... b){ cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; }template<class... T> constexpr auto Min(T... a){ return min(initializer_list<common_type_t<T...>>{a...}); }template<class... T> constexpr auto Max(T... a){ return max(initializer_list<common_type_t<T...>>{a...}); }template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }template<class T> bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }struct settings{ settings(){ ios_base::sync_with_stdio(0); cin.tie(0); cout<<fixed<<setprecision(15); }; }settingss;const double PI = acos(-1);const int INF = 1001001001;const ll LINF = 1001001001001001001LL;const int mod = 1000000007;class modint {long long x;public:modint(long long x=0) : x((x%mod+mod)%mod) {}modint operator-() const {return modint(-x);}modint& operator+=(const modint& a) {if ((x += a.x) >= mod) x -= mod;return *this;}modint& operator-=(const modint& a) {if ((x += mod-a.x) >= mod) x -= mod;return *this;}modint& operator*=(const modint& a) {(x *= a.x) %= mod;return *this;}modint operator+(const modint& a) const {modint res(*this);return res+=a;}modint operator-(const modint& a) const {modint res(*this);return res-=a;}modint operator*(const modint& a) const {modint res(*this);return res*=a;}modint pow(ll t) const {if (!t) return 1;modint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}modint inv() const {return pow(mod-2);}modint& operator/=(const modint& a) {return (*this) *= a.inv();}modint operator/(const modint& a) const {modint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const modint& m){os << m.x;return os;}};vector<long long> divisor(long long n) {vector<long long> ret;for (ll i = 1; 1LL*i*i <= n; i++) if (n%i == 0) { ret.push_back(i); if (i*i != n) ret.push_back(n / i); }sort(ret.begin(), ret.end());return ret;}modint dp[100100];int main() {int M; cin >> M;dp[0] = 1;Rep(i, 1, M+1) {vll D = divisor(i);fore(d, D) {dp[i] += dp[i/d - 1];}}cout << dp[M] << endl;}