結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
![]() |
提出日時 | 2020-08-12 04:33:59 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 483 ms / 2,000 ms |
コード長 | 10,916 bytes |
コンパイル時間 | 16,489 ms |
コンパイル使用メモリ | 264,404 KB |
最終ジャッジ日時 | 2025-01-12 21:06:01 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
コンパイルメッセージ
main.cpp:1:13: warning: extra tokens at end of #ifdef directive 1 | #ifdef MAIN ================================================================================================================================ | ^~ main.cpp:25:8: warning: extra tokens at end of #endif directive [-Wendif-labels] 25 | #endif MAIN ================================================================================================================================ | ^~~~ main.cpp:54:13: warning: integer suffix 'z' shadowed by implementation 54 | inline lint operator""z(const unsigned long long n){ return lint(n); } | ^~~~~~~~
ソースコード
#ifdef MAIN ================================================================================================================================+library{ name:mint, url:"https://tqkoh.github.io/library/library/lib/util/mint.hpp", version:"2020-08-08" }int solve(){lin(N);cs s(N,'9');lint n=s.size();vector<vector<mint>>dp0(n+10,vector<mint>(10)),dp1(n+10,vector<mint>(10));dp0[0][0] = 1;rep(n){rep(j,10){rep(l,j,10)dp1[i+1][l] += dp1[i][j];rep(l,j,s[i]-'0')dp1[i+1][l] += dp0[i][j];lint l = s[i]-'0';if(j<=l)dp0[i+1][l] += dp0[i][j];}}mint ans=0;rep(j,10)ans+=dp0[n][j]+dp1[n][j];out(ans);return 0;}#endif MAIN ================================================================================================================================//sub-BOF// desktop// author: Tqk//#define _AOJ_#define _C_INPUT_// #pragma region template// #pragma region basic#define IN_FILE "./in.txt"//#pragma GCC optimize ("O3")#pragma warning(disable: 4455 4244 4067 4068 4996)#pragma GCC target ("avx")#pragma GCC diagnostic ignored "-Wliteral-suffix"#define NOMINMAX#ifdef _ENV_TQK_#include <Windows.h>#endif#include "bits/stdc++.h"using namespace std;typedef int64_t lint;typedef long double ld;typedef string cs;#define linf 1152921504606846976#ifndef _AOJ_inline lint operator""z(const unsigned long long n){ return lint(n); }#endiftemplate<class T>inline T operator-(const vector<T>& a,const size_t&i){return a.at(i);}// #pragma endregion// #pragma region rep#define _vcppunko3(tuple) _getname3 tuple#define _vcppunko4(tuple) _getname4 tuple#define _getname4(_1,_2,_3,_4,name,...) name#define _getname3(_1,_2,_3,name,...) name#define _trep2(tuple) _rep2 tuple#define _trep3(tuple) _rep3 tuple#define _trep4(tuple) _rep4 tuple#define _rep1(n) for(lint i=0;i<n;++i)#define _rep2(i,n) for(lint i=0;i<n;++i)#define _rep3(i,a,b) for(lint i=a;i<b;++i)#define _rep4(i,a,b,c) for(lint i=a;i<b;i+=c)#define _tper2(tuple) _per2 tuple#define _tper3(tuple) _per3 tuple#define _tper4(tuple) _per4 tuple#define _per1(n) for(lint i=n-1;i>=0;--i)#define _per2(i,n) for(lint i=n-1;i>=0;--i)#define _per3(i,a,b) for(lint i=b-1;i>=a;--i)#define _per4(i,a,b,c) for(lint i=a+(b-a-1)/c*c;i>=a;i-=c)#define rep(...) _vcppunko4((__VA_ARGS__,_trep4,_trep3,_trep2,_rep1))((__VA_ARGS__))#define per(...) _vcppunko4((__VA_ARGS__,_tper4,_tper3,_tper2,_per1))((__VA_ARGS__))#define _tall2(tuple) _all2 tuple#define _tall3(tuple) _all3 tuple#define _all1(v) v.begin(),v.end()#define _all2(v,a) v.begin(),v.begin()+a#define _all3(v,a,b) v.begin()+a,v.begin+b#define all(...) _vcppunko3((__VA_ARGS__,_tall3,_tall2,_all1))((__VA_ARGS__))#define each(c) for(auto &e:c)// #pragma endregion// #pragma region iotemplate<class T>istream& operator>>(istream& is,vector<T>& vec);template<class T,size_t size>istream& operator>>(istream& is,array<T,size>& vec);template<class T,class L>istream& operator>>(istream& is,pair<T,L>& p);template<class T>ostream& operator<<(ostream& os,vector<T>& vec);template<class T,class L>ostream& operator<<(ostream& os,pair<T,L>& p);template<class T>istream& operator>>(istream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }template<class T,class L>istream& operator>>(istream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }template<class T,class L>ostream& operator<<(ostream& os,pair<T,L>& p){ os<<p.first<<" "<<p.second;return os; }template<class T>ostream& operator<<(ostream& os,vector<T>& vec){ os<<vec[0];rep(i,1,vec.size())os<<' '<<vec[i];return os; }template<class T>ostream& operator<<(ostream& os,deque<T>& deq){ os<<deq[0];rep(i,1,deq.size())os<<' '<<deq[i];return os; }template<class T>ostream& operator<<(ostream& os,set<T>& s){ each(s)os<<e<<" ";return os; }#ifdef _ENV_TQK_/*ifstream infile(IN_FILE);template<class T>ifstream& operator>>(ifstream& is,vector<T>& vec);template<class T,size_t size>ifstream& operator>>(ifstream& is,array<T,size>& vec);template<class T,class L>ifstream& operator>>(ifstream& is,pair<T,L>& p);template<class T>ifstream& operator>>(ifstream& is,vector<T>& vec){ for(T& x: vec) is>>x;return is; }template<class T,class L>ifstream& operator>>(ifstream& is,pair<T,L>& p){ is>>p.first;is>>p.second;return is; }inline void fin(){}template <class Head,class... Tail>inline void fin(Head&& head,Tail&&... tail){ infile>>head;fin(move(tail)...); }*///#include<Windows.h>HANDLE hConsole = GetStdHandle(STD_OUTPUT_HANDLE);inline void in(){ SetConsoleTextAttribute(hConsole,10); }template <class Head,class... Tail>inline void in(Head&& head,Tail&&... tail){SetConsoleTextAttribute(hConsole,15);cin>>head;in(move(tail)...);}#elseinline void in(){}template <class Head,class... Tail>inline void in(Head&& head,Tail&&... tail){ cin>>head;in(move(tail)...); }#endifinline bool out(){ return(cout<<'\n',0); }template <class T>inline bool out(T t){ return(cout<<t<<'\n',0); }template <class Head,class... Tail>inline bool out(Head head,Tail... tail){ cout<<head<<' ';out(move(tail)...);return 0; }template <class T>inline void alloc(T &c,lint s){ rep(c.size())c[i].resize(s); }#define alc alloc#ifdef _ENV_TQK_inline bool deb(){ SetConsoleTextAttribute(hConsole,10); return(cout<<'\n',0); }template <class T>inline bool deb(T t){ return(SetConsoleTextAttribute(hConsole,12),cout<<t<<'\n',SetConsoleTextAttribute(hConsole,10),0); }template <class Head,class... Tail>inline bool deb(Head head,Tail... tail){SetConsoleTextAttribute(hConsole,12);cout<<head<<' ';deb(move(tail)...);return 0;}#define dsp(ex) sp(ex)#define dno(ex) no(ex)#define look(v) SetConsoleTextAttribute(hConsole,12),cout<<#v<<": ",deb(v);#else#define deb(...) 0#define dsp(ex) 0#define dno(ex) 0#define look(v) 0#endif// #pragma endregion// #pragma region TA#define lin(...) lint __VA_ARGS__;in(__VA_ARGS__)#define stin(...) string __VA_ARGS__;in(__VA_ARGS__)#define vin(type,name,size) vector<type> name(size);in(name)#define pb push_back#define fi e.first#define se e.second#define YES(c) cout<<((c)?"YES\n":"NO\n"),0#define Yes(c) cout<<((c)?"Yes\n":"No\n"),0#define POSSIBLE(c) cout<<((c)?"POSSIBLE\n":"IMPOSSIBLE\n"),0#define Possible(c) cout<<((c)?"Possible\n":"Impossible\n"),0#define o(p) cout<<p<<endl,0#define sp(p) cout<<p<<" ",0#define no(p) cout<<p,0#define st(v) sort(all(v))#define psort(l,r) if(l>r)swap(l,r);#define fn(ty1,ty2,ex) [&](ty1 l,ty2 r){ return(ex); }#define lfn(ex) [&](lint l,lint r){ return(ex); }// #pragma endregion// #pragma region funcinline constexpr lint gcd(lint a,lint b){ while(b){ lint c=b;b=a%b;a=c; }return a; }inline constexpr lint lcm(lint a,lint b){ return a/gcd(a,b)*b; }template<typename T>inline constexpr bool chmin(T &mn,const T &cnt){ if(mn>cnt){ mn=cnt;return 1; } else return 0; }template<typename T>inline constexpr bool chmax(T &mx,const T &cnt){ if(mx<cnt){ mx=cnt;return 1; } else return 0; }// #pragma endregion// #pragma region Pclass P{ public:lint f,s; P(lint a,lint b):f(a),s(b){}; P():f(0),s(0){}; };istream& operator>>(istream& os,P& p){ os>>p.f>>p.s;return os; }inline constexpr bool operator<(const P& l,const P& r){ return(l.f-r.f?l.f<r.f:l.s<r.s); }inline constexpr bool operator>(const P& l,const P& r){ return(l.f-r.f?l.f>r.f:l.s>r.s); }inline constexpr bool operator==(const P& l,const P& r){ return(l.f==r.f&&l.s==r.s); }inline constexpr bool operator!=(const P& l,const P& r){ return(l.f!=r.f||l.s!=r.s); }inline P operator+(const P& l,const P& r){return P(l.f+r.f,l.s+r.s);}inline P operator-(const P& l,const P& r){return P(l.f-r.f,l.s-r.s);}inline P operator-(const P& r){return P(-r.f,-r.s); }inline P operator*(const lint& l,const P& r){return P(l*r.f,l*r.s); }inline P operator/(const P& l,const lint& r){return P(l.f/r,l.s/r); }inline ld abs(P p){return sqrtl(p.f*p.f+p.s*p.s);}inline ld mabs(P p){return abs(p.f)+abs(p.s);}inline ld mht(P x,P y){return mabs(x-y);}// #pragma endregion// #pragma region startstruct Start{Start(){#ifndef _C_INPUT_cin.tie(0),cout.tie(0);ios::sync_with_stdio(0);#endifcout<<fixed<<setprecision(16);}} __start;// #pragma endregion// #pragma endregion// #pragma region const#define mod 1000000007const ld pi=acos(-1);const ld tau=(1.+sqrtl(5))/2.;P d4[4]={P(1,0),P(0,1),P(-1,0),P(0,-1)};P d8[8]={P(1,0),P(1,1),P(0,1),P(-1,1),P(-1,0),P(-1,-1),P(0,-1),P(1,-1)};const cs AUTO_YES = "Yes";const cs AUTO_NO = "No";int cho(bool c,cs yes=AUTO_YES,cs no=AUTO_NO){return out((c?yes:no));}// #pragma endregion// #pragma region solve// #pragma region lib_mint#define md_tmp template<uint_fast64_t md=mod>md_tmp class modint{using u64 = uint_fast64_t;public:u64 a;constexpr modint(const lint x = 0) noexcept: a((x+md)%md){}constexpr u64& value() noexcept{ return a; }constexpr const u64& value() const noexcept{ return a; }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 lint 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{a += rhs.a;if(a>=md)a -= md;return *this;}constexpr modint& operator-=(const modint rhs) noexcept{if(a<rhs.a)a += md;a -= rhs.a;return *this;}constexpr modint& operator*=(const modint rhs) noexcept{a = a*rhs.a%md;return *this;}constexpr modint& operator^=(const lint rhs) noexcept{if(!rhs)return *this = 1;u64 exp = rhs-1;modint base = a;while(exp){if(exp&1)*this *= base;base *= base;exp >>= 1;}return *this;}constexpr modint& operator/=(const modint rhs) noexcept{a = (*this*(rhs^(md-2))).a;return *this;}};md_tmp istream& operator>>(istream& os,modint<md>& m){os>>m.a,m.a %= md;return os;}md_tmp ostream& operator<<(ostream& os,const modint<md>& m){return os<<m.a;}using mint = modint<>;#ifndef _AOJ_mint operator""m(unsigned long long n){ return mint(n); }#endif/** @title Mint* @see https://noshi91.hatenablog.com/entry/2019/03/31/174006*/// #pragma endregionint solve(){lin(N);cs s(N,'9');lint n=s.size();vector<vector<mint>>dp0(n+10,vector<mint>(10)),dp1(n+10,vector<mint>(10));dp0[0][0] = 1;rep(n){rep(j,10){rep(l,j,10)dp1[i+1][l] += dp1[i][j];rep(l,j,s[i]-'0')dp1[i+1][l] += dp0[i][j];lint l = s[i]-'0';if(j<=l)dp0[i+1][l] += dp0[i][j];}}mint ans=0;rep(j,10)ans+=dp0[n][j]+dp1[n][j];out(ans);return 0;}// #pragma endregion// #pragma region mainint main(){solve();}// #pragma endregion//sub-EOF