ll dp[20][2][180]
int solve(string &n,int idx=0,int tight=1,int sum=0){
if(idx==sz(n)) return sum;
if(dp[idx][tight][sum]!=-1) return dp[idx][tight][sum];
int lo = 0;
int hi = tight? n[idx]-'0':9;
ll ans = 0;
for(int i=lo;i<=hi;i++){
ans+=solve(n,idx+1,tight&&(hi==i),sum+i);
}
return dp[idx][tight][sum] = ans;
}
int query(string a,string b){ // return sum of digits of numbers from a to b
return solve(b) - solve(a);
}
If number of digits of a & b are same = n
ll dp[DIG][m][2][2];
ll solve(int idx,int r=0,bool tightl=1,bool tightr=1){
if(idx==n) return r==0;
if(dp[idx][r][tightl][tightr]) return dp[idx][r][tightl][tightr];
int lo = tightl ? a[idx]-'0':0;
int hi = tightr ? b[idx]-'0':9;
ll cnt=0;
for(int i=lo;i<=hi;i++){
if(idx%2==0 && i==d) continue;
if(idx%2==1 && i!=d) continue;
int newr = (r*10+i)%m;
cnt=add(cnt,solve(idx+1,newr,tightl&&i==lo,tightr&&i==hi));
}
return dp[idx][r][tightl][tightr]=cnt;
}
A Digit-Immune number is a number which is not divisible by any of its digits.
A digit-immune number will be called an odd-digit-immune number if it contains only odd digits.
LCM Trick: Check divisibility
</br></br></br>
const int LCM = 63;
int ALLMASK = 1<<4;
ll dp[DIG][2][LCM+1][ALLMASK+1];
ll solve(int idx,bool tight,int r,int mask,int prev){
if(idx==n){
for(int d=0;d<4;d++){
int di = d*2+3;
if(di!=5 && mask&(1<<d) && rem%di==0) return 0;
if(di==5 && prev==5) return 0;
}
return 1;
}
if(dp[idx][tight][r][mask]!=-1) return dp[idx][tight][r][mask];
int lo = tight && a[idx]<'3' ? 10:3;
int hi = tight ? a[idx]-'0':9;
ll cnt=0;
if(mask==0) cnt+=solve(idx+1,0,r,0,0);
for(int di=lo;di<=hi;di+=2){
int d=(di-3)/2;
int newr = (r*10+di)%LCM;
int newtight = tight&&(di==hi);
cnt+= solve(idx+1,newtight,newr,mask|(1<<d),d);
}
return dp[idx][tight][r][mask]=cnt;
}
Determine number of pairs (x,y) s.t 0<=x<y<=n, S(x) < S(y).
</br>
Trick for pair-digit-dp is to maintain dp[curr_idx][i>L][i<R][j>L][j<R]
</br>
int del = 250*9;
ll dp[255][del*2+5][2][2];
void solve(int idx,bool tightx,bool tighty,int diff=del){
if(dp[idx][tightx][tighty][diff]!=-1) return dp[idx][tightx][tighty][diff];
if(idx==m) return diff>del;
int xlo = 0;
int xhi = tightx ? a[idx]-'0':9;
ll cnt=0;
for(int i=xlo;i<=xhi;i++){
int ylo = 0;
int yhi = tighty ? i:9;
for(int j=ylo;j<=yhi;j++){
cnt = add(cnt,solve(idx+1,tightx && i==xhi,tighty && j==yhi,diff+i-j));
}
}
return dp[idx][tightx][tighty][diff] = cnt;
}
a+b=a^b => a&b=0 from sum-xor property
query(L,R): # pairs(a,b) s.t a in [0,L] and b in [0,R] and a&b=0.
ans(L,R) = query(L,R) - query(R,L-1) - query(L,R-1) + query(L-1,L-1);