deushiro

xd

Dec 28th, 2019
233
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 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[0] - 48; ++i){
  11.         ans += dp[s.size()][i];
  12.         ans %= mod;
  13.     }
  14.     for(int i = 1; i < s.size(); ++i){
  15.         if (s[i] < s[i - 1])
  16.             break;
  17.         for(int j = s[i - 1] - 48; j < s[i] - 48 + (i == s.size() - 1); ++j){
  18.             ans += dp[s.size() - i][j];
  19.             ans %= mod;
  20.         }
  21.     }
  22.     return ans;
  23. }
  24.  
  25. int main() {
  26.     string a, b;
  27.     cin >> a >> b;
  28.     vector<vector<int>> dp(b.size() + 1, vector<int>(10));
  29.     dp[1][1] = 1;
  30.     for(int i = 1; i < 10; ++i){
  31.         dp[1][i] = 1;
  32.     }
  33.     for(int i = 2; i < dp.size(); ++i){
  34.         for(int j = 1; j < 10; ++j){
  35.             for(int k = j; k < 10; ++k){
  36.                 dp[i][j] += dp[i - 1][k];
  37.                 dp[i][j] %= mod;
  38.             }
  39.         }
  40.     }
  41.     int ans;
  42.     cout << dp[1][3] << endl;
  43.     cout << f("135", dp);
  44. }
Advertisement
Add Comment
Please, Sign In to add comment