I am trying to solve this problem http://www.spoj.com/problems/NUMTSN/ on spoj. I tried to use dynamic programming. I am getting TLE. Here is my code:
int MOD = 1000000007 int MA = 100 int dp[54][2][18][18][18]; vi a; int num; int solve(int index, int free, int t,int s, int n) { if(t > 17 || s > 17 || n > 17) return 0;
//DBG(index);
if(index == num)
{
//DBG(index);
if(t >= 1 && (t == s) && (s == n))
return 1;
return 0;
}
int &ret = dp[index][free][t][s][n];
if(ret != -1) return ret;
ret = 0;
int nfree,nt,ns,nn;
for(int i = 0; i < 10; i++)
{
nfree = free | (i < a[index]);
nt = t + ( (i == 3) ? 1 : 0); //DBG(nt);
ns = s + ( (i == 6) ? 1 : 0); //DBG(ns);
nn = n + ( (i == 9) ? 1 : 0); //DBG(nn);
if(free)
{
ret = ((ret % MOD) + (solve(index+1, nfree, nt, ns, nn)) % MOD) % MOD;
}
else
{
if( i <= a[index])
ret = (ret % MOD + (solve(index+1, nfree, nt, ns, nn)) % MOD ) % MOD;
}
}
return (ret% MOD);
} void convert(char* m) { a.clear(); int l = strlen(m); for(int i = 0; i < l; i++) a.pb( (m[i] — '0')); //reverse(all(a)); num = sz(a); }
void decrement(char* s) { int l = strlen(s)-1; int g = s[l] — '0'; int b = 0;
if(g != 0)
{
g--;
s[l] = g + '0';
}
else
{
g = 9;
s[l] = g + '0';
l--; b = 1;
}
while( b != 0 && l >= 0)
{
int g = s[l] - '0';
if( g != 0)
{
g --;
s[l] = g + '0';
b = 0;
}
else
{
g = 9;
s[l] = g + '0';
b = 1; l--;
}
}
} int main() { int te; cin >> te; while(te--) { char x[MA],y[MA]; cin >> x >> y; decrement(x); //int l = strlen(x); /*for(int i = 0; i < l; i++) cout << x[i]; cout << endl;*/ convert(x); memset(dp,-1,sizeof dp); int ans1 = solve(0,0,0,0,0);
convert(y);
memset(dp,-1,sizeof dp);
int ans2 = solve(0,0,0,0,0);
cout << ((ans2 - ans1)%MOD+MOD)%MOD << endl;
}
return 0;
}