fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int MAX = 1e4+7;
  4. const int MOD = 1e9 +7;
  5. string ss;
  6. int dp[100001][5][9];
  7.  
  8. int solve(int i,int j,int mod)
  9. {
  10.   if(dp[i][j][mod]!=-1) return dp[i][j][mod];
  11.   if(i==ss.length() || j==5) return 0;
  12.   int mn = 0,pp = 0;
  13.   pp = (mod*10 + ss[i] - '0')%9;
  14.   //nah nah you would be counting the same steps again...
  15.  
  16.   if(pp==0) mn++;
  17.   mn += (solve(i+1,j+1,pp) + solve(i+1,0,0)%MOD)%MOD; //case 1 if u are not ignoring...
  18.   dp[i][j][mod] = (mn + solve(i+1,j,mod)%MOD)%MOD; // case 2 if u are ignoring...
  19.   return mn;
  20. }
  21.  
  22. int main()
  23. {
  24.   ios_base::sync_with_stdio(false);
  25.   cin.tie(0); cout.tie(0);
  26.   int t;
  27.   cin>>t;
  28.   while(t-->0)
  29.   {
  30.     cin>>ss;
  31.     memset(dp,-1,sizeof(dp));
  32.     int  p = 0;
  33.     for(int i = 0;i<ss.length();i++) if((ss[i]-'0')==0) p++;
  34. 	  cout<<solve(0,0,0)-(1<<p - 1)<<'\n';
  35.   }
  36.   return 0;
  37. }
  38.  
Success #stdin #stdout 0.01s 21068KB
comments (?)
stdin
copy 
2
10292
0189
stdout
copy 
5
9
https://ideone.com/QvllsH
language:
C++14 (gcc 8.3)
created:
3 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!