fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define br cout<<"\n";
  4. #define inf 9e17
  5. #define ninf -9e17
  6. #define int long long int
  7. const long long INF = 9e17;
  8. #define MOD 1000000007
  9. #define pb push_back
  10. #define ff first
  11. #define ss second
  12. #define FIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  13. #define count1 __builtin_popcount()
  14. const int N = 1e6 + 5;
  15. #define rchild 2*pos+2
  16. #define lchild 2*pos+1
  17. string a,b;
  18. vector <int> v;
  19. int n;
  20. int dp[51][51][51][51][2];
  21. int di[20];
  22. int size = 0;
  23. /*
  24. ----------------------------------------------------------------------------------------------------------------------------------
  25. */
  26. //functions
  27. void convert(string s){
  28.     v.clear();
  29.     for(int i = 0;i < s.size();i++){
  30.         v.push_back(s[i] - '0');
  31.     }
  32.     n = v.size();
  33.     memset(dp,-1,sizeof(dp));
  34. }
  35. int solve(int idx,int c3,int c6,int c9,int tight){
  36.     //cout << idx << '\n';
  37.     if(idx == n){
  38.         return ((c3 == c6) and (c3 == c9) and (c3 >= 1));
  39.     }
  40.     if(dp[idx][c3][c6][c9][tight] != -1){
  41.         return dp[idx][c3][c6][c9][tight];
  42.     }
  43.     int lim = (tight)?v[idx]+1:10,res = 0;
  44.     for(int i = 0;i < lim;i++){
  45.         int newtight;
  46.           if(v[idx] == i)
  47.             newtight = tight;
  48.           else
  49.             newtight = 0;
  50.         res+=(solve(idx+1,(i==3)+c3,(i==6)+c6,(i==9)+c9,newtight))%MOD;
  51.         res %= MOD;
  52.     }
  53.     dp[idx][c3][c6][c9][tight] = res;
  54.     return res;
  55. }
  56. bool check(string s){
  57.     int c3=0,c6=0,c9=0;
  58.     for(int i = 0;i < s.size();i++){
  59.        if(s[i] == '3')
  60.        c3++;
  61.        if(s[i] == '6')
  62.        c6++;
  63.        if(s[i] == '9')
  64.        c9++;
  65.     }
  66.     if( c3 == c6 and c3 == c9 and c3 >= 1){
  67.         return true;
  68.     }
  69.     return false;
  70. }
  71. /*
  72. main ----------------------------------------------------------------------------------------------------------------------------------
  73. */
  74. int32_t main(){
  75.     int t;
  76.     cin >> t;
  77.     while(t--){
  78.         string a,b;
  79.         cin >> a >> b;
  80.         convert(b);
  81.         int ans1 = solve(0,0,0,0,1);
  82.         convert(a);
  83.         int ans2 = solve(0,0,0,0,1);
  84.         int  ans = (ans1 - ans2 + MOD)%MOD;
  85.         if(check(a)){
  86.             ans = (ans + 1)%MOD;
  87.         }
  88.         cout << ans <<endl;
  89.     }
  90. }
Success #stdin #stdout 1.18s 108812KB
comments (?)
stdin
copy 
50
46493012504740240 8493515924263178869169044262237335838584676805585
340297391635826866842177240524303599 21813189596691281859122863113149839463
3 11547103395795875234637363651969473724483899
94291187238343662189025712753477114512591527429 7831329875186809657367866936233847465036700159873
3761681032693496438 3365108411101112984003525539863634872368105805174
51975929697847426725666826700817 3863256627307794302940340019323252
24 96637139850887566553676772116417398929347
75224526659 59864433926889859441870050556802946554032067667865
1334 664509
711576065417 16897130667768299
782 22030913184162239338497935752582879733742478
2087945387445 2644395650340688588
900985 4921168825863237644319
222966579080811647640 9570667965486489907623393202663031230281
88458318441999334973854517 22106965739806976534666225385033410759750
57 1301716879616386787114254501
484918 083428905060202531466536564262034564
6001153801361988096470118588103 21358193741611922045598252403411483650924915079
4445461110433616 071357103368512366605221521961511325525346
04 14552
60133947014 2197888190769655247618917835671396081034
79514418882719324497 9771925017190125473656631907818710256
7810764393114 6415805256791708169077578586178204
8429369464837925794088712359 055639280633790793206626479869005
1224298231291591722744 03611045923596724015430355968188
4432475763247772151247775 0843297895101639072508868355823394108953976468110
093062684050401 89071879848749965362
91 841715517587571300709558766327968
0548266080391823993092 854356358683263413405887627000766662965222500041
134269738720 0278901317665024848873032588951125843036
1753967216699861 65061342595895544193398969424164079933762207
13 1633232095256645371
58779500036708712507151 7427202586905425257973193084243
358580079819103994 4144179338592200462321184871899318
1201414318631646087 93993742834717191198910438136050872806839
337271 687325977382488087780861955444583631470
3512305329783707431745620278949348961287 70067342013160769838316490316024731389001
2169359506 5626416210991161708188256
9636158038556406286074821004363 344358958538340805411725657589883
94573743796717969647640601651 54299096380465970262419561909535662730469609139
0552813004709801522200 30334516817505290389752585046098779721463646160
80672 0754269701704520443153394925581084702165816210181
84534411252254475 4759620262827338592624426324
3190 93376436662682403282152883266031083769640
451 16582511939498365066785734685971290342852061453
45303787244 14211957021419725570292194544151
3541446372611913525697590 868615981661260188472543896318
69971925005 24917465661643089531791604856295
00748831691429438 42924020868867706928269
71729688 0825234992765967696516950415548901736689263001966
stdout
copy 
10828164
359701845
554507088
224022635
153325690
216776885
311761874
40437629
25911
907988599
244514327
814297458
61963198
62916869
159273134
466110196
63928488
89525889
220698665
230
108221382
961810369
594240685
409694958
318242112
58416662
134366255
511029969
237962245
526365386
131867163
19920155
811537914
89270737
34588134
710898635
25659503
427383891
192951267
868918490
341457224
340080747
345792463
967017007
592501795
628320060
339973950
277221828
982406914
295960229
https://ideone.com/oamcbn
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

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!