Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- const int MOD = 1e9 + 7;
- int n , A , B , timer;
- vector < int > v[33];
- const int MXN = 8 , MXL = 9;
- pair < int , int > I[33];
- int dp[MXL + 1][MXN + 1][(1<<MXN)+1][11][MXN + 1][2];
- int vi[MXL + 1][MXN + 1][(1<<MXN)+1][11][MXN + 1][2];
- void Set(int idx , int V){
- v[idx].clear();
- while(V > 0){
- v[idx].push_back(V % 10);
- V /= 10;
- }
- while(v[idx].size() < MXL) v[idx].push_back(0);
- }
- int stop;
- int calc(int pos , int num , int mask , int sum , int carry , int zflag){
- int &ret = dp[pos][num][mask][sum][carry][zflag];
- int &ttt = vi[pos][num][mask][sum][carry][zflag]; if(ttt == timer) return ret;
- ttt = timer; ret = 0;
- if(pos == stop){
- if( ((zflag || sum == 0) || (sum >= A && sum <= B)) && (mask == (1<<n) - 1) )
- ret = 1;
- return ret;
- }
- if(num == n){
- if(sum == 0 && carry == 0 && pos > 0) return ret = calc(pos + 1 , 0 , mask , 0 , 0 , 1);
- if( (sum > 0 || carry > 0) && zflag && A != 0) return ret = 0;
- if(sum >= A && sum <= B) return ret = calc(pos + 1 , 0 , mask , carry , 0 , 0);
- return ret = 0;
- }
- int nmask = 0;
- for(int dig = 0 ; dig < 10 ; dig++){
- if(dig == v[num][pos]) nmask = mask;
- else if(dig < v[num][pos]) nmask = (mask | (1<<num));
- else nmask = (mask & ~(1<<num));
- ret += calc(pos , num + 1 , nmask , (sum + dig)%10 , carry + (sum + dig)/10 , zflag);
- ret %= MOD;
- }
- return ret;
- }
- void solve(){
- long long ans = 0;
- cin>>n>>A>>B;
- for(int j = 0 ; j < n ; j++){
- cin>>I[j].first>>I[j].second;
- }
- for(int mask = 0 ; mask < (1<<n) ; mask++){
- int par = __builtin_popcount(mask) % 2;
- bool skip = 0;
- for(int j = 0 ; j < n ; j++){
- if( (mask & (1<<j)) ){
- if(I[j].first == 0){
- skip = 1;
- break;
- }
- else Set(j , I[j].first - 1);
- }
- else {
- Set(j , I[j].second);
- }
- }
- if(skip) continue;
- stop = 1;
- for(int j = 0 ; j < n ; j++)
- for(int i = 0 ; i < MXL ; i++)
- if(v[j][i] != 0)
- stop = max(stop , i + 1);
- ++timer;
- int A = calc(0 , 0 , (1<<n) - 1 , 0 , 0 , 0);
- if(!par) ans += A;
- else ans -= A , ans += MOD;
- ans += MOD;
- ans %= MOD;
- }
- cout<<ans<<endl;
- }
- int main(){
- //freopen("in.in","r",stdin);
- int T;
- cin>>T;
- while(T--) solve();
- }
Add Comment
Please, Sign In to add comment