I Came to know about Digit DP from this blog https://mirror.codeforces.com/blog/entry/53960 and I Tried the following problem on DIGIT DP as given in the blog https://vjudge.net/problem/LightOJ-1068
here is my code I am Getting TLE on it Please Help Me!!!
Your code here...
#include<iostream>
#include<cstring>
#include<vector>
#define ll long long
using namespace std;
vector<int > num;
void convert(ll n){
vector<int > g;
while(n>0){
g.push_back(n%10);
n/=10;
}
for(int i=g.size()-1;i>=0;i--) num.push_back(g[i]);
}
ll a,b,k;
ll DP[20][200][200][2];
ll call(int pos,int nmodk,int digmodk,int flag){
if(pos==num.size()){
if(nmodk%k==0 && digmodk%k==0)
return 1;
return 0;
}
if(DP[pos][nmodk][digmodk][flag]!=-1)
return DP[pos][nmodk][digmodk][flag];
int lmt=9;
if(!flag)
lmt=num[pos];
int ans=0;
for(int dgt=0;dgt<=lmt;dgt++){
int nflag=flag;
int nnmodk=(((nmodk%k)*(10%k))%k+dgt%k)%k;
int ddigmodk=(digmodk%k+dgt%k)%k;
if(flag==0 && dgt<lmt) nflag=1;
ans+=call(pos+1,nnmodk,ddigmodk,nflag);
}
DP[pos][nmodk][digmodk][flag]=ans;
return ans;
}
ll solve(ll b){
num.clear();
memset(DP,-1,sizeof(DP));
convert(b);
return call(0,0,0,0);
}
int main(){
ll t;
cin>>t;
int p=0;
while(t--){
cin>>a>>b>>k;
cout<<"Case "<<p<<": "<<solve(b)-solve(a-1);
p++;
}
return 0;
}
1) nigga you are mad. this line itself will TLE the whole problem, change it to this:
2) max B is 2^31-1, so max length of your number is 10. max sum of digits is (1 + 9*9) = 82, => max k = 82 => max remainder for both sum of digits and your number is 82
3) remove unnecessary long longs. max range is [1; 2^31-1], => max dp is 2^31-1, which is exactly INT_MAX
4) after all of this your dp will look like this:
so there are max 11*83*83*2 combinations of parameters instead of 11*83*200*2 — roughly 2.5 times less operations for your calculating function and ~ 10 times less operations for cleaning up after the test is done(20*200*200*2 -> 11*83*83*2)
also we changed 8 mod operations to 2 for every iteration of for in your call(which is actually calc, lmao), so it must be approximately 4 times less operations, since mod is the slowest simple operation in your code
summing up this, you reduce the time of execution of your program in 10 times(even more if you are not scared of overflow and will change ll to int)
Cin and cout is slow, better use scanf or add this to your code after the main:
ios_base::sync_with_stdio(0);cin.tie(0);