fork download
copy 
  1. // g++ -std=c++17 in.cpp -o test
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. //defs
  6. using ll = long long;
  7. using uint = unsigned int;
  8. #define rep(i,n) for(int i=0;i<int(n);i++)
  9. #define per(i,n) for(int i=int(n)-1;i>=0;i--)
  10. #define all(c) c.begin(),c.end()
  11. #define si(x) int(x.size())
  12. #define pb emplace_back
  13. #define fs first
  14. #define sc second
  15.  
  16.  
  17. //helper
  18. template<class T> using V = vector<T>;
  19. template<class T> using VV = vector<vector<T>>;
  20. template<class T,class U> void chmax(T& x, U y){if(x<y) x=y;}
  21. template<class T,class U> void chmin(T& x, U y){if(y<x) x=y;}
  22. template<class T> void mkuni(V<T>& v){sort(all(v));v.erase(unique(all(v)),v.end());}
  23.  
  24. //debug print
  25. template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){
  26. 	return o<<"("<<p.fs<<","<<p.sc<<")";
  27. }
  28.  
  29. template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){
  30. 	o<<"{";
  31. 	for(const T& v:vc) o<<v<<",";
  32. 	o<<"}";
  33. 	return o;
  34. }
  35.  
  36. const ll mod = 1e9+7;
  37.  
  38. ll gcd (ll a, ll b) {
  39.     return b ? gcd (b, a % b) : a;
  40. }
  41.  
  42. ll binpow(ll a, ll b, ll m) {
  43.     a %= m;
  44.     ll res = 1;
  45.     while (b > 0) {
  46.         if (b & 1)
  47.             res = res * a % m;
  48.         a = a * a % m;
  49.         b >>= 1;
  50.     }
  51.     return res;
  52. }
  53.  
  54. const int MAXN = 2e5+1;
  55.  
  56. vector<bool> a_p((1<<10),false), b_p((1<<10),false), f_p((1<<10),false);
  57.  
  58. long long dp[20][(1<<10)][2];
  59.  
  60. void getDigits(long long x, vector <int> &digit)
  61. {
  62.     while (x)
  63.     {
  64.         digit.push_back(x%10);
  65.         x /= 10;
  66.     }
  67. }
  68.  
  69. long long digitSum(int idx, int cur, int tight,vector <int> &digit, bool non_zero)
  70. {
  71.     // base case
  72.     if (idx == -1){
  73.         // if( cur % 2 == 0)
  74.         if( f_p[cur] ){
  75.             return 1;
  76.         }else
  77.             return 0;
  78.     }
  79.  
  80.     // checking if already calculated this state
  81.     if (dp[idx][cur][tight] != -1 and tight != 1)
  82.         return dp[idx][cur][tight];
  83.  
  84.     long long ret = 0;
  85.  
  86.     // calculating range value
  87.     int k = (tight)? digit[idx] : 9;
  88.  
  89.     for (int i = 0; i <= k ; i++)
  90.     {
  91.         // calculating newTight value for next state
  92.         int newTight = (digit[idx] == i)? tight : 0;
  93.         // fetching answer from next state
  94.         if( non_zero ){
  95.             ret += digitSum(idx-1, cur|(1<<i), newTight, digit, true);
  96.         }else{
  97.             if( i ){
  98.                 ret += digitSum(idx-1, cur|(1<<i), newTight, digit, true);
  99.             }else{
  100.                ret += digitSum(idx-1, cur, newTight, digit, false); 
  101.             }
  102.         }
  103.         ret %= mod;
  104.     }
  105.  
  106.     if (!tight)
  107.       dp[idx][cur][tight] = ret;
  108.  
  109.     return ret;
  110. }
  111.  
  112. int main(){
  113. 	cout<<fixed<<setprecision(9);
  114. 	int test =  1;
  115. 	cin>>test;
  116. 	for(int t=1; t<=test; t++){
  117.         int n, m;
  118.         cin>>n>>m;
  119.         vector<ll> a(n) , b(m);
  120.  
  121.         for(int i=0;i<(1<<10);i++){
  122.             a_p[i] = b_p[i] = f_p[i] = false;
  123.         }
  124.  
  125.         for(int i=0;i<n;i++){
  126.             cin>>a[i];
  127.             int cur = 0;
  128.             while( a[i] > 0){
  129.                 cur |= (1<<(a[i]%10));
  130.                 a[i] /= 10;
  131.             }
  132.             a_p[cur] = true;
  133.             if( cur % 2)
  134.                 a_p[cur-1] = true;
  135.         }
  136.  
  137.         for(int i=0;i<m;i++){
  138.             cin>>b[i];
  139.             int cur = 0;
  140.             while( b[i] > 0){
  141.                 cur |= (1<<(b[i]%10));
  142.                 b[i] /= 10;
  143.             }
  144.             b_p[cur] = true;
  145.             if( cur % 2)
  146.                 b_p[cur-1] = true;
  147.         }
  148.  
  149.         for(int i=0;i<(1<<10);i++){
  150.             for(int j=0;j<(1<<10);j++){
  151.                 f_p[(i|j)] = f_p[(i|j)] or (a_p[i] and b_p[j]);
  152.             }
  153.         }
  154.  
  155.         ll l , r;
  156.         cin>> l >> r;
  157.         --l;
  158.         vector<int> digitA;
  159.         memset(dp, -1, sizeof(dp));
  160.         getDigits(l, digitA);
  161.         long long ans1 = digitSum(digitA.size()-1, 0, 1, digitA, false);
  162.         vector<int> digitB;
  163.         memset(dp, -1, sizeof(dp));
  164.         getDigits(r, digitB);
  165.         long long ans2 = digitSum(digitB.size()-1, 0, 1, digitB, false);
  166.         ll num = ( ans2 - ans1 + mod ) %mod;
  167.         cout<<num<<"\n";  
  168. 	}
  169. 	return 0;
  170. }
Runtime error #stdin #stdout 0.83s 2096008KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7qJerO
language:
C++ (gcc 8.3)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!