1068 - Investigation, C++ (gcc)

1068 - Investigation

// BISMILLAHIR RAHMANIR RAHIM
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
 
#define inf 0x3f3f3f3f
 
#define PI acos(-1)
#define eps 1e-9
//#define inf 100000000
#define MOD 1000000007
 
#define mem(a,b) memset(a, b, sizeof(a) )
 
int dx[] = {0, 0, +1, -1};
int dy[] = {+1, -1, 0, 0};
//int dx[] = {+1, 0, -1, 0, +1, +1, -1, -1};
//int dy[] = {0, +1, 0, -1, +1, -1, +1, -1};
 
inline bool EQ(double a, double b) { return fabs(a-b) < eps; }
//
//debug
#ifdef HELLO
template < typename F, typename S >
ostream& operator << ( ostream& os, const pair< F, S > & p ) {
            return os << "(" << p.first << ", " << p.second << ")";
}
 
template < typename T >
ostream &operator << ( ostream & os, const vector< T > &v ) {
            os << "{";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << *it;
                                            }
                    return os << "}";
}
 
template < typename T >
ostream &operator << ( ostream & os, const set< T > &v ) {
            os << "[";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << *it;
                                            }
                    return os << "]";
}
 
template < typename F, typename S >
ostream &operator << ( ostream & os, const map< F, S > &v ) {
            os << "[";
                for(auto it = v.begin(); it != v.end(); ++it) {
                                if( it != v.begin() ) os << ", ";
                                        os << it -> first << " = " << it -> second ;
                                            }
                    return os << "]";
}
 
#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
 
void faltu () {
            cerr << endl;
}
 
template <typename T>
void faltu( T a[], int n ) {
            for(int i = 0; i < n; ++i) cerr << a[i] << ' ';
                cerr << endl;
}
 
template <typename T, typename ... hello>
void faltu( T arg, const hello &... rest) {
            cerr << arg << ' ';
                faltu(rest...);
}
#else
#define dbg(args...)
#endif // HELLO
 
int biton(int N, int pos) {return N = N | (1 << pos);}
int bitoff(int N, int pos) {return N = N & ~(1 << pos);}
bool check(int N, int pos) {return (bool)(N & (1 << pos));}
 
#define ll long long int
#define ff first
#define ss second
#define sc(a)           scanf("%d", &a)
#define sc2(a, b)       scanf("%d%d", &a, &b)
#define sc3(a, b, c)    scanf("%d%d%d", &a, &b, &c)
#define SS(a) scanf("%lli", &a)
#define P(a) printf("%i", a)
#define PP(a) printf("%lli", a)

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define REP(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define MX 90

ll dp[MX][2][MX][MX]; // pos, first, restricted, sum, rem
bool vis[MX][2][MX][MX];
int length, k;
ll a, b;
vector <int > v;

ll call(int pos, int f1, int sum, int rem){
    if(pos == length){
        if( sum % k == 0 and rem % k == 0) return 1;
        else return 0;
    }

ll &ret = dp[pos][f1][sum][rem];
    bool &vi = vis[pos][f1][sum][rem];

if(vi) return ret;

vi = true;

ll ans = 0;

int kk = f1 ? 9 : v[pos];

for(int i = 0; i <= kk; i++){
        ans += call(pos + 1, i < v[pos] ? 1 : f1, (sum + i) % k, (rem * 10 + i) % k);
    }
    
    return ret = ans;

}

ll process(ll x){
    length = 0;
    v.clear();
    while(x){
        v.push_back(x % 10);
        length++;
        x /= 10;
    //  dbg(x);
    }
    mem(vis, false);
    reverse(v.begin(), v.end());
    return call(0, 0, 0, 0);
}

int main(){
    
    int t, cs = 0;
    sc(t);
    while(t--){
        SS(a); SS(b); sc(k);
        printf("Case %i: %lli\n", ++cs, process(b) - process(a - 1));
    }

//fprintf(stderr, "Time: %d ms\n", (int)(clock()*1000.0/CLOCKS_PER_SEC));
    return 0;
}


run \| edit \| history \| help	0