結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
![]() |
提出日時 | 2020-05-20 00:33:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 209 ms / 2,000 ms |
コード長 | 7,055 bytes |
コンパイル時間 | 1,784 ms |
コンパイル使用メモリ | 180,568 KB |
実行使用メモリ | 144,124 KB |
最終ジャッジ日時 | 2024-10-01 23:21:58 |
合計ジャッジ時間 | 6,265 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include <bits/stdc++.h>#include <algorithm>#include <cmath>#include <set>#include <cstdio>#include <vector>#include <iostream>#include <utility>#include <queue>#include <map>#include <complex>#define fir first#define sec second#define sz(s) (s).size()#define pb push_back#define get(n) scanf("%d",&n);#define gets(s) string s;cin >> (s);#define prfi(n) printf("%d", &n);#define prfd(n) printf("%lf", &n);#define All(s) (s).begin(), (s).end()#define rep(i,j) for(int (i)=0;(i)<(j);(i)++)#define For(i,j,k) for(int (i)=(j);(i)<(k);(i)++)#define drep(i,j) for(int (i)=(j);(i)>=0;(i)--)#define Ford(i,j,k) for(int (i)=(j);i>=(k);i--)#define fore(c,v) for(auto (c): (v))#define lp for(int __=0;__<n;i++)#define mem(a,b) memset(a,b,sizeof(a));#define dump(x) std::cout << #x << " = " << (x) << std::endl;#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;using ull = unsigned long long int;using ll = long long;using ld = long double;using pii = std::pair<int,int>;using pll = std::pair<ll, ll>;using vi = std::vector<int> ;using vvi = std::vector<vi> ;using vll = std::vector<ll>;using vvll = std::vector<vll>;using vd = std::vector<double> ;using vvd = std::vector<vd> ;using qi = std::queue<int> ;using vpii = std::vector<std::pair<int, int> >;using vpll = std::vector<pll>;using namespace std;const int Mod = (1e9) + 7;const int INF = 1e9 + 19;const ll INFL = 1e18 + 19;const int dx[] = {-1, 0, 0, 1};const int dy[] = {0, -1, 1, 0};const int dx2[] = {-1, -1, -1, 0, 0, 0, 1, 1, 1};const int dy2[] = {1, 0, -1, 1, 0, -1, 1, 0, -1};const double EPS = 1e-10;//_____________________________________Templates_________________________________________//template<class T1, class T2> inline void chmin(T1 &a, T2 b){if(a > b) a = b;}template<class T1, class T2> inline void chmax(T1 &a, T2 b){if(a < b) a = b;}template<class T> inline void pri(T a){cout << a << endl;}template<class Z> using vec = vector<Z>;template<class T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;//mainly use for dynamic progtemplate<class T1, class T2>void update(T1 &a, T2 b){a += b;if(a > Mod) a %= Mod;}inline void IN(void){return;}template <typename First, typename... Rest>void IN(First& first, Rest&... rest){cin >> first;IN(rest...);return;}inline void OUT(void){cout << "\n";return;}template <typename First, typename... Rest>void OUT(First first, Rest... rest){cout << first << " ";OUT(rest...);return;}bool pairsort(pll pl, pll pr){if(pl.first == pr.first)return pl.second > pr.second;return pl.first < pr.first;}int cntbit(ll a,int n,int j){int res = 0;For(i,j,n){if(a>>i & 1){res++;}}return res;}vector<int> make_bit(int a){vector<int> res; for(int i=31;i>=0;i--)if(a&(1<<i))res.pb(i);return res;}bool stdbit(int a, int b){return a&(1 << b); }int GCD(int a, int b){if(b > a)return GCD(b,a);if(a%b == 0)return b;else return GCD(b, a%b);}int LCM(int a, int b){return a*b/GCD(a,b);}int roundup(int a, int b){if(a % b == 0)return a/b;else return (a+b)/b;}int rounddown(int a, int b){if(a%b == 0)return a/b;else {return (a-b)/b;}}ll pow(ll a, ll n){ll res = 1;while(n > 0){if(n&1)res *= a; a *= a; n = n >> 1;}return res;}ll GetDiviserCount(ll N)//約数の個数{ll res = 1;For(i,2,sqrt(N)+1){ll cnt = 0;while(N%i == 0){cnt++;N /= i;}res *= (cnt + 1);if(N == 1)break;}if(N != 1)res *= 2;return res;}vll GetDivisor(ll N)//約数列挙{vll res;for(ll i = 1;i*i <= N;i++){if(N%i == 0){res.pb(i);if(i*i != N)res.pb(N/i);}}sort(All(res));return res;}struct mint {ll x; // typedef long long ll;mint(ll x=0):x((x%Mod+Mod)%Mod){}mint operator-() const { return mint(-x);}mint& operator+=(const mint a) {if ((x += a.x) >= Mod) x -= Mod;return *this;}mint& operator-=(const mint a) {if ((x += Mod-a.x) >= Mod) x -= Mod;return *this;}mint& operator*=(const mint a) {(x *= a.x) %= Mod;return *this;}mint operator+(const mint a) const {mint res(*this);return res+=a;}mint operator-(const mint a) const {mint res(*this);return res-=a;}mint operator*(const mint a) const {mint res(*this);return res*=a;}mint pow(ll t) const {if (!t) return 1;mint a = pow(t>>1);a *= a;if (t&1) a *= *this;return a;}// for prime modmint inv() const {return pow(Mod-2);}mint& operator/=(const mint a) {return (*this) *= a.inv();}mint operator/(const mint a) const {mint res(*this);return res/=a;}friend ostream& operator<<(ostream& os, const mint& a);};ostream& operator<<(ostream& os, const mint& a){os << a.x;return os;}struct combination {vector<mint> fact, ifact;combination(int n):fact(n+1),ifact(n+1) {assert(n < Mod);fact[0] = 1;for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;ifact[n] = fact[n].inv();for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;}mint operator()(int n, int k) {if (k < 0 || k > n) return 0;return fact[n]*ifact[k]*ifact[n-k];}};using vm = vector<mint>;using vvm = vector<vm>;template<class Z>struct MyMatrix{using mat = MyMatrix<Z>;vector<vector<Z>> m_dat;int m_h;int m_w;MyMatrix(int h, int w) : m_h(h), m_w(w) ,m_dat(h,vector<Z>(w)) {}vector<Z> &operator[] (int idx){return m_dat[idx];}mat Multiple(mat &a){mat C(m_h, a.m_w);for(int i=0;i<m_h;i++){for(int j=0;j<a.m_w;j++){for(int k=0;k<m_w;k++){C[i][j] += m_dat[i][k] * a[k][j];}}}return C;}mat Pow(ll x){mat B(m_h,m_w);for(int i=0;i<m_h;i++){B[i][i] = 1;}mat A = *this;while(x > 0){if(x&1)B = B.Multiple(A);A = A.Multiple(A);x = x >> 1;}return B;}//friend ostream& operator<<(ostream &os, const mat &A);};/*template<class Z>ostream& operator<<(ostream &os, Matrix<Z>& A){for(int i=0;i<A.m_h;i++){for(int j=0;j<A.m_w;j++){os << A[i][j] << " ";}os << endl;}return os;}*/template<class T>using mat = MyMatrix<T>;//_____________________ following sorce code_________________________//const int max_n = 3 * (1e5) + 1;const int max_m = 83 * (1e5) + 1;int n,m,k;ll N;int h,w;string S;int a,b,c;vi v;int ans;double x,y,z;vector<int> G[1010101];signed main (int argc, char* argv[]) {cin.tie(0);ios::sync_with_stdio(false);IN(n);vec<vm> dp(n+1,vm(10));rep(i,10){dp[0][i] = 1;}For(i,1,n){rep(j,10){For(k,0,j+1){dp[i][j] += dp[i-1][k];}}}mint ans = 0;rep(j,10){ans += dp[n-1][j];}pri(ans);//for(auto c : ans){cout << c << endl;}//cout << fixed << setprecision(15) << ans << endl;return 0;}