### taklo's blog

By taklo, history, 4 months ago, ,

I Came to know about Digit DP from this blog https://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

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;
}


• +6

 » 4 months ago, # |   0 Auto comment: topic has been updated by taklo (previous revision, new revision, compare).
 » 4 months ago, # | ← Rev. 5 →   +10 int nnmodk=(((nmodk%k)*(10%k))%k+dgt%k)%k; int ddigmodk=(digmodk%k+dgt%k)%k;1) nigga you are mad. this line itself will TLE the whole problem, change it to this: int nnmodk = (nmodk*10 + dgt)%k; int ddigmodk = (digmodk + dgt)%k;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 823) remove unnecessary long longs. max range is [1; 2^31-1], => max dp is 2^31-1, which is exactly INT_MAX4) after all of this your dp will look like this: dp[11][83][83][2]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 codesumming 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)
•  » » 4 months ago, # ^ |   0 Thank You Sir for helping!!
 » 4 months ago, # |   0 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);
•  » » 4 months ago, # ^ |   0 I just forgot about it Thanks