Advertisement
deushiro

Untitled

Dec 31st, 2019
217
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.15 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5.  
  6. const int mod = 1e9 + 7;
  7.  
  8. int f(string s, vector<vector<int>> &dp){
  9.     int ans = 0;
  10.     for(int i = 1; i <= s.size() - 1; ++i){
  11.         for(int j = 1; j <= 9; ++j){
  12.             ans += dp[i][j];
  13.             ans %= mod;
  14.         }
  15.     }
  16.     for(int i = 1; i < s[0] - 48; ++i){
  17.         ans += dp[s.size()][i];
  18.         ans %= mod;
  19.     }
  20.     for(int i = 1; i < s.size(); ++i){
  21.         if (s[i] < s[i - 1])
  22.             break;
  23.         for(int j = s[i - 1] - 48; j < s[i] - 48 ; ++j){  // + (i == s.size() - 1)
  24.             ans += dp[s.size() - i][j];
  25.             ans %= mod;
  26.         }
  27.     }
  28.     return ans;
  29. }
  30.  
  31. int main() {
  32.     string a, b;
  33.     cin >> a >> b;
  34.     vector<vector<int>> dp(b.size() + 1, vector<int>(10));
  35.     dp[1][1] = 1;
  36.     for(int i = 1; i < 10; ++i){
  37.         dp[1][i] = 1;
  38.     }
  39.     for(int i = 2; i < dp.size(); ++i){
  40.         for(int j = 1; j < 10; ++j){
  41.             for(int k = j; k < 10; ++k){
  42.                 dp[i][j] += dp[i - 1][k];
  43.                 dp[i][j] %= mod;
  44.             }
  45.         }
  46.     }
  47.     int ans;
  48.     cout << dp[1][3] << endl;
  49.     cout << f("11", dp);
  50. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement