結果
問題 | No.741 AscNumber(Easy) |
ユーザー |
![]() |
提出日時 | 2019-07-30 22:18:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 648 ms / 2,000 ms |
コード長 | 818 bytes |
コンパイル時間 | 1,573 ms |
コンパイル使用メモリ | 167,684 KB |
実行使用メモリ | 160,420 KB |
最終ジャッジ日時 | 2024-07-05 06:14:47 |
合計ジャッジ時間 | 11,311 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 55 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef long long ll;typedef long double ld;#define rep(i, n) for (ll i = 0; i < n; i++)#define FOR(i, a, b) for (ll i = a; i < b; i++)#define len(v) ll(v.size())#define fi first#define se secondtemplate <class T>void cout_vec(const vector<T> &vec){for(auto itr:vec) cout<<itr<<' ';cout<<'\n';}typedef pair<ll,ll> P;const ll mod=1e9+7;ll dp[1000010][2][10];int main(){cin.tie(0);ios::sync_with_stdio(false);int n;cin>>n;string s;rep(i,n) s.push_back('9');dp[0][0][0]=1;rep(i,n)rep(j,2)rep(k,10){int x=s[i]-'0';for(int l=k;l<=(j?9:x);l++){(dp[i+1][j||(l<x)][l]+=dp[i][j][k])%=mod;}}ll ans=0;rep(k,10) (ans+=(dp[n][0][k]+dp[n][1][k])%mod)%=mod;cout<<ans<<endl;}