結果
問題 | No.1407 Kindness |
ユーザー |
![]() |
提出日時 | 2021-02-26 22:29:33 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 21 ms / 2,000 ms |
コード長 | 1,349 bytes |
コンパイル時間 | 1,436 ms |
コンパイル使用メモリ | 163,436 KB |
実行使用メモリ | 8,960 KB |
最終ジャッジ日時 | 2024-10-02 15:14:52 |
合計ジャッジ時間 | 2,741 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}#define ll long long#define double long double#define rep(i,n) for(int i=0;i<(n);i++)#define REP(i,n) for(int i=1;i<=(n);i++)#define mod (ll)(1e9+7)#define inf (ll)(3e18+7)#define eps (double)(1e-9)#define pi (double) acos(-1)#define P pair<int,int>#define PiP pair<int,pair<int,int>>#define all(x) x.begin(),x.end()#define rall(x) x.rbegin(),x.rend()using namespace std;int main() {string s;cin >> s;int n = s.size();vector<vector<ll>> dp(n+1, vector<ll>(2, 0));rep(i, n){int now = s[i] - '0';rep(x, 10){if(x < now){dp[i+1][0] += (dp[i][0] * x) % mod;dp[i+1][0] += (dp[i][1] * x) % mod;}else if(x == now){dp[i+1][0] += (dp[i][0] * x) % mod;dp[i+1][1] += (dp[i][1] * x) % mod;if(i == 0)dp[i+1][1] += x;}else{dp[i+1][0] += (dp[i][0] * x) % mod;}if(i || x < now)dp[i+1][0] += x;dp[i+1][1] %= mod;dp[i+1][0] %= mod;}}cout << (dp[n][0] + dp[n][1]) % mod << endl;}