結果
問題 | No.1407 Kindness |
ユーザー |
![]() |
提出日時 | 2021-02-26 22:11:03 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 165 ms / 2,000 ms |
コード長 | 1,933 bytes |
コンパイル時間 | 1,055 ms |
コンパイル使用メモリ | 95,500 KB |
実行使用メモリ | 43,680 KB |
最終ジャッジ日時 | 2024-10-02 14:59:07 |
合計ジャッジ時間 | 3,978 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <iostream>#include <vector>#include <string>#include <algorithm>#include <iomanip>#include <map>#include <queue>#include <functional>using namespace std;using ll = long long int;using P = pair<int, int>;constexpr ll MOD = 1000000007;ll solve0(string n){ll ans = 0;for(ll i = 1; i <= stoi(n); i++){ll tmp = i;ll coans = 1;while(tmp){coans *= (tmp%10);tmp /= 10;}ans += coans;}return ans;}ll solve1(string n0){vector<int> n;n.push_back(0);for(auto &p: n0) n.push_back(p-'0');vector<vector<vector<ll>>> memo(n.size(), vector<vector<ll>>(2, vector<ll>(10, -1)));function<ll(int, int, int)> f = [&](int i, int smaller, int j){if(memo[i][smaller][j] != -1) return memo[i][smaller][j];memo[i][smaller][j] = 0;if(i == n.size()-1) memo[i][smaller][j] = j;else if(smaller == 1){for(int subj = 0; subj < 10; subj++){memo[i][smaller][j] += f(i+1, 1, subj) * j;memo[i][smaller][j] %= MOD;}}else{for(int subj = 0; subj < n[i+1]; subj++){memo[i][smaller][j] += f(i+1, 1, subj) * j;memo[i][smaller][j] %= MOD;}memo[i][smaller][j] += f(i+1, 0, n[i+1]) * j;memo[i][smaller][j] %= MOD;}//cerr << i << " " << smaller << " " << j << " " << memo[i][smaller][j] << endl;return memo[i][smaller][j];};ll ans = 0;for(int i = 0; i < n[1]; i++) ans += f(1, 1, i);ans += f(1, 0, n[1]);for(int i = 2; i < n.size(); i++){for(int j = 0; j < 10; j++) ans += f(i, 1, j);ans %= MOD;}//cerr << f(1, 0, 1) << endl;return ans%MOD;}int main(){string n;cin >> n;// cerr << solve0(n) << endl;cout << solve1(n) << endl;return 0;}