Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define pb push_back
- #define all(c) c.begin(),c.end()
- #define f first
- #define s second
- using namespace std;
- typedef long long ll;
- const ll INF64 = 1e18 + 1337;
- const int INF32 = 1e9 + 228;
- const int MOD = 1e9 + 7;
- void plusOne(string& s)
- {
- s[s.length() - 1]++;
- int i = s.length() - 1;
- while(s[i] > '9')
- {
- if(i == 0)
- {
- string h = "1";
- for(int j = 0; j < s.length(); j++)
- h += "0";
- s = h;
- return;
- }
- s[i] = '0';
- s[i - 1]++;
- i--;
- }
- }
- ll formula(ll n, ll fd)
- {
- ll res = 1;
- set<ll> divide;
- for(int i = 2; i <= n - 1; i++)
- {
- divide.insert(i);
- }
- for(int k = 10 - fd; k < 9 + n - fd; k++)
- {
- res *= k;
- set<ll> buf;
- for(auto& it : divide)
- {
- if(res % it == 0)
- {
- res /= it;
- buf.insert(it);
- }
- }
- for(auto& it : buf)
- {
- divide.erase(it);
- }
- res %= MOD;
- //cerr << n << " " << fd << " " << res << "\n";
- }
- return res;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- #ifndef __WIN32
- ifstream cin("input.txt");
- ofstream cout("output.txt");
- #endif
- cin.tie(0);cout.tie(0);
- string l, r;
- cin >> l >> r;
- ///move l to number like 10000000..
- ///move r to number like 9999999..
- if(r.size() <= 4)
- {
- ll ans = 0;
- do
- {
- bool tooManyBooleans = 0;
- for(int i = 1; i < l.length(); i++)
- {
- if(l[i] < l[i - 1])
- {
- tooManyBooleans = 1;
- break;
- }
- }
- if(!tooManyBooleans) ans++;
- if(l==r) break;
- plusOne(l);
- }while(1);
- cout << ans;
- return 0;
- }
- bool gofuckyourself = 0;
- for(int i = 1; i < r.size(); i++)
- {
- if(r[i - 1] > r[i])
- {
- gofuckyourself = 1;
- break;
- }
- }
- if(gofuckyourself)
- {
- string buf = "";
- for(int i = 0; i < r.size() - 1; i++)
- buf += "9";
- r = buf;
- }
- ll sum = 0;
- for(int n = l.size(); n <= r.size(); n++)
- {
- ll st = 1, en = 9;
- for(int fd = st; fd <= en; fd++)
- {
- sum += formula(n, fd);
- sum %= MOD;
- }
- }
- cout << sum;
- #ifndef __WIN32
- cin.close();
- cout.close();
- #endif
- return 0;
- }
- ///(9 + n - fd)!/((10 - fd)!*(n - 1)!)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement