Guest User

Untitled

a guest
Dec 24th, 2018
133
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MOD = 1e9 + 7;
  4.  
  5. int n , A , B , timer;
  6.  
  7. vector < int > v[33];
  8.  
  9. const int MXN = 8 , MXL = 9;
  10.  
  11. pair < int , int > I[33];
  12.  
  13.  
  14. int dp[MXL + 1][MXN + 1][(1<<MXN)+1][11][MXN + 1][2];
  15. int vi[MXL + 1][MXN + 1][(1<<MXN)+1][11][MXN + 1][2];
  16.  
  17.  
  18. void Set(int idx , int V){
  19.  
  20.     v[idx].clear();
  21.  
  22.     while(V > 0){
  23.         v[idx].push_back(V % 10);
  24.         V /= 10;
  25.     }
  26.  
  27.     while(v[idx].size() < MXL) v[idx].push_back(0);
  28.  
  29. }
  30.  
  31. int stop;
  32.  
  33. int calc(int pos , int num , int mask , int sum , int carry , int zflag){
  34.  
  35.     int &ret = dp[pos][num][mask][sum][carry][zflag];
  36.  
  37.     int &ttt = vi[pos][num][mask][sum][carry][zflag]; if(ttt == timer) return ret;
  38.  
  39.     ttt = timer; ret = 0;
  40.  
  41.     if(pos == stop){
  42.         if( ((zflag || sum == 0) || (sum >= A && sum <= B)) && (mask == (1<<n) - 1) )
  43.             ret = 1;
  44.         return ret;
  45.     }
  46.  
  47.     if(num == n){
  48.  
  49.         if(sum == 0 && carry == 0 && pos > 0) return ret = calc(pos + 1 , 0 , mask , 0 , 0 , 1);
  50.  
  51.         if( (sum > 0 || carry > 0) && zflag && A != 0) return ret = 0;
  52.  
  53.         if(sum >= A && sum <= B) return ret = calc(pos + 1 , 0 , mask , carry , 0 , 0);
  54.  
  55.         return ret = 0;
  56.  
  57.     }
  58.  
  59.     int nmask = 0;
  60.  
  61.     for(int dig = 0 ; dig < 10 ; dig++){
  62.  
  63.         if(dig == v[num][pos]) nmask = mask;
  64.         else if(dig < v[num][pos]) nmask = (mask | (1<<num));
  65.         else nmask = (mask & ~(1<<num));
  66.  
  67.         ret += calc(pos , num + 1 , nmask , (sum + dig)%10 , carry + (sum + dig)/10 , zflag);
  68.         ret %= MOD;
  69.     }
  70.  
  71.     return ret;
  72.  
  73.  
  74.  
  75.  
  76.  
  77. }
  78.  
  79.  
  80. void solve(){
  81.  
  82.  
  83.  
  84.  
  85.     long long ans = 0;
  86.  
  87.     cin>>n>>A>>B;
  88.  
  89.     for(int j = 0 ; j < n ; j++){
  90.         cin>>I[j].first>>I[j].second;
  91.     }
  92.  
  93.     for(int mask = 0 ; mask < (1<<n) ; mask++){
  94.  
  95.         int par = __builtin_popcount(mask) % 2;
  96.  
  97.         bool skip = 0;
  98.  
  99.         for(int j = 0 ; j < n ; j++){
  100.             if( (mask & (1<<j)) ){
  101.                 if(I[j].first == 0){
  102.                     skip = 1;
  103.                     break;
  104.                 }
  105.                 else Set(j , I[j].first - 1);
  106.             }
  107.             else {
  108.                 Set(j , I[j].second);
  109.             }
  110.         }
  111.  
  112.         if(skip) continue;
  113.  
  114.         stop = 1;
  115.  
  116.         for(int j = 0 ; j < n ; j++)
  117.             for(int i = 0 ; i < MXL ; i++)
  118.                 if(v[j][i] != 0)
  119.                     stop = max(stop , i + 1);
  120.  
  121.         ++timer;
  122.  
  123.         int A = calc(0 , 0 , (1<<n) - 1 , 0 , 0 , 0);
  124.  
  125.  
  126.         if(!par) ans += A;
  127.         else ans -= A , ans += MOD;
  128.  
  129.  
  130.         ans += MOD;
  131.         ans %= MOD;
  132.  
  133.     }
  134.  
  135.     cout<<ans<<endl;
  136.  
  137. }
  138. int main(){
  139.     //freopen("in.in","r",stdin);
  140.  
  141.  
  142.     int T;
  143.     cin>>T;
  144.     while(T--) solve();
  145.  
  146.  
  147.  
  148. }
RAW Paste Data