Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int mod = 1e9 + 7;
- int f(string s, vector<vector<int>> &dp){
- int ans = 0;
- for(int i = 1; i <= s.size() - 1; ++i){
- for(int j = 1; j <= 9; ++j){
- ans += dp[i][j];
- ans %= mod;
- }
- }
- for(int i = 1; i < s[0] - 48; ++i){
- ans += dp[s.size()][i];
- ans %= mod;
- }
- for(int i = 1; i < s.size(); ++i){
- if (s[i] < s[i - 1])
- break;
- for(int j = s[i - 1] - 48; j < s[i] - 48 ; ++j){ // + (i == s.size() - 1)
- ans += dp[s.size() - i][j];
- ans %= mod;
- }
- }
- return ans;
- }
- int main() {
- string a, b;
- cin >> a >> b;
- vector<vector<int>> dp(b.size() + 1, vector<int>(10));
- dp[1][1] = 1;
- for(int i = 1; i < 10; ++i){
- dp[1][i] = 1;
- }
- for(int i = 2; i < dp.size(); ++i){
- for(int j = 1; j < 10; ++j){
- for(int k = j; k < 10; ++k){
- dp[i][j] += dp[i - 1][k];
- dp[i][j] %= mod;
- }
- }
- }
- int ans;
- cout << dp[1][3] << endl;
- cout << f("11", dp);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement