Light OJ 1068 / Digit DP

/***
 created: 2022-09-07-23.20.28
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

ll dp[12][100][100][3],k;

vector<ll>digit;

ll solve(ll in,ll sum,ll num, bool f)
{
    if(in==digit.size())
    {
        if (sum%k==0 && num%k==0) return 1;
        else return 0;
    }

    if(dp[in][sum][num][f]!=-1) return dp[in][sum][num][f];

    ll ans=0;

    ll lim;

    if(f) lim=9;
    else lim=digit[in];

    for(ll i=0;i<lim;i++)
    {
        ans+=solve(in+1,(sum+i),(num*10 + i)%k, 1);
    }

    ans+=solve(in+1,(sum+lim),(num*10 + lim)%k, f);

    return dp[in][sum][num][f]=ans;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);


    test
    {
        ll n,m,i,a,b,ans;

        cin>>a>>b>>k;

        if(k>=99)
        {
            cout<<"Case "<<cs<<": "<<0<<nl;
            continue;
        }


        digit.clear();
        memset(dp,-1,sizeof dp);
        while(b)
        {
            digit.push_back(b%10);
            b/=10;
        }
        reverse(digit.begin(),digit.end());


        ans=solve(0,0,0,0);


        digit.clear();
        memset(dp,-1,sizeof dp);
        a-=1;
        while(a)
        {
            digit.push_back(a%10);
            a/=10;
        }
        reverse(digit.begin(),digit.end());


        ans = ans - solve(0,0,0,0);

        cout<<"Case "<<cs<<": "<<ans<<nl;
    }


    get_lost_idiot;
}