結果
問題 | No.1581 Multiple Sequence |
ユーザー |
|
提出日時 | 2021-07-02 21:59:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 88 ms / 2,000 ms |
コード長 | 3,588 bytes |
コンパイル時間 | 1,988 ms |
コンパイル使用メモリ | 198,648 KB |
最終ジャッジ日時 | 2025-01-22 16:00:57 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> typedef uint64_t u64; typedef int64_t i64; typedef long double f128; using namespace std; template<u64 mod> struct modint{ u64 val; constexpr modint(const i64 x=0) noexcept:val((x%i64(mod)+i64(mod))%i64(mod)){} constexpr u64 &value() noexcept{ return val; } constexpr modint operator+(const modint rhs) const noexcept{ return modint(*this)+=rhs; } constexpr modint operator-(const modint rhs) const noexcept{ return modint(*this)-=rhs; } constexpr modint operator*(const modint rhs) const noexcept{ return modint(*this)*=rhs; } constexpr modint operator/(const modint rhs) const noexcept{ return modint(*this)/=rhs; } constexpr modint &operator+=(const modint rhs) noexcept{ val+=rhs.val; val-=((val>=mod)?mod:0); return *this; } constexpr modint &operator-=(const modint rhs) noexcept{ val+=((val<rhs.val)?mod:0); val-=rhs.val; return *this; } constexpr modint &operator*=(const modint rhs) noexcept{ val=val*rhs.val%mod; return *this; } constexpr modint &operator/=(modint rhs) noexcept{ u64 exp=mod-2; while(exp){ if(exp&1){ (*this)*=rhs; } rhs*=rhs; exp>>=1; } return *this; } friend constexpr ostream &operator<<(ostream &os,const modint &x) noexcept{ return os<<(x.val); } friend constexpr istream &operator>>(istream &is,modint &x) noexcept{ u64 t; is>>t; x=t; return is; } }; template<typename T> void scan(T& n){ cin>>n; } void scan(){} template<typename T,class... Args> void scan(T& n,Args&... args){ scan(n); scan(args...); } template<typename T> void scanall(T start,T end){ for(;start!=end;++start){ scan(*start); } } template<typename T> void print(T n){ cout<<n; } void print(){} template<typename T,class... Args> void print(T n,Args... args){ print(n); print(args...); } template<typename T> void println(T n){ print(n); cout<<endl; } template<typename T,class... Args> void println(T n,Args... args){ print(n,' '); println(args...); } template<typename T> void printall(T start,T end){ if(start!=end){ print(*start); for(++start;start!=end;++start){ print(' ',*start); } } cout<<endl; } template<typename T> void chmax(T& n,T m){ n=max(n,m); } template<typename T> void chmin(T& n,T m){ n=min(n,m); } template<typename T> T power(T a,i64 n){ T res=1; while(n){ res*=(n&1)?a:1; a*=a; n>>=1; } return res; } i64 power(i64 a,i64 n,i64 m){ i64 res=1; while(n){ res=res*((n&1)?a:1)%m; a=a*a%m; n>>=1; } return res; } template<typename T> struct combination{ vector<T> fact; combination(const int mx=3000000):fact(mx+1,1){ for(int i=2;i<=mx;++i){ fact[i]=fact[i-1]*i; } } template<typename U> T nCk(U n,U k){ if(n<k||n<0||k<0){ return 0; } return fact[n]/fact[k]/fact[n-k]; } }; void solve(); int main(){ cout<<fixed<<setprecision(15); bool is_multicase=false; int T=1; if(is_multicase){ scan(T); } for(int i=0;i<T;++i){ solve(); } return 0; } vector<int> div_enum(int N){ vector<int> res; for(int i=1;i*i<=N;++i){ if(N%i!=0){ continue; } res.emplace_back(i); if(i*i!=N){ res.emplace_back(N/i); } } return res; } void solve(){ typedef modint<1000000007> mint; int M; scan(M); vector<mint> dp(M+1); dp[0]=1; dp[1]=1; for(int i=2;i<=M;++i){ vector<int> vec=div_enum(i); for(int x:vec){ dp[i]+=dp[i/x-1]; } } println(dp[M]); }