結果
問題 | No.1407 Kindness |
ユーザー |
![]() |
提出日時 | 2021-02-26 21:29:43 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 75 ms / 2,000 ms |
コード長 | 872 bytes |
コンパイル時間 | 3,637 ms |
コンパイル使用メモリ | 257,032 KB |
最終ジャッジ日時 | 2025-01-19 04:48:40 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 36 |
ソースコード
#include <stdio.h>#include <atcoder/all>#include <bits/stdc++.h>using namespace std;using namespace atcoder;using mint = modint1000000007;#define rep(i,n) for (int i = 0; i < (n); ++i)#define Inf 1000000001string N;mint get(int ind,int f){if(ind==N.size())return 1;static vector dp(200000,vector<mint>(2,0));static vector visited(200000,vector<bool>(2,false));if(visited[ind][f])return dp[ind][f];visited[ind][f] = true;mint ret = 0;rep(i,10){int t = N[ind] - '0';if(i<t){ret += get(ind+1,1) * i;}else if(i==t){ret += get(ind+1,f) * i;}else{if(f==0)continue;ret += get(ind+1,f) * i;}}dp[ind][f] = ret;return ret;}int main(){cin>>N;//reverse(N.begin(),N.end());mint ans = get(0,0);rep(i,N.size()){ans += mint(45).pow(i);}ans--;cout<<ans.val()<<endl;return 0;}