[Codeforces] E. Salazar Slytherin's Locket

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Salazar Slytherin's Locket
Source            : Codeforces
Category          : Dynamic Programing
Algorithm         : Digit DP
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
 
ll dp[12][70][(1<<10)+5]; // dp[ base ][ pos ][ mask ]
bool memoize[12][70][(1<<10)+5];
int a[65];
 
inline ll solvedp(int base, int pos, int mask = 0, bool small = 1, bool take = 0)
{
      if (pos < 0) return mask == 0;
      ll &ret = dp[base][pos][mask];
      bool &mem = memoize[base][pos][mask];
      if (!small && take && mem) return ret;
      int loop = base - 1;
      if (small) loop = a[pos];
      ll sum = 0;
      for (int i = 0; i <= loop; i++)
      {
            if (!take && i == 0) sum += solvedp(base, pos-1, 0, 0, 0);
            else sum += solvedp(base, pos-1, mask ^ (1 << i), small && i == a[pos], 1);
      }
      if (take && !small) mem = 1, ret = sum;
      return sum;
}
 
inline ll solve(int base, ll x)
{
      int len = 0;
      while (x)
      {
            a[len++] = x % base;
            x /= base;
      }
      return solvedp(base, len - 1, 0, 1, 0);
}
 
int main()
{
      //freopen("in.txt", "r", stdin);

      memset(memoize, 0, sizeof memoize);
      int tc;
      scanf("%d", &tc);
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            int base;
            ll num1, num2;
            scanf("%d %lld %lld", &base, &num1, &num2);
            printf("%lld\n", solve(base, num2) - solve(base, num1-1));
      }
      return 0;
}