[toph.co] Noora Number

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Noora Number
Source            : toph.co
Category          : Dynamic Programing
Algorithm         : Digit DP
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll        long long
 
ll dp[70][(1<<10)+5]; // dp[ pos ][ mask ]
bool memoize[70][(1<<10)+5];
int a[22];
 
inline ll solvedp(int pos, int mask = 0, bool small = 1, bool take = 0)
{
      if (pos < 0)
      {
            int maxdigit = -1;
            int distinctdigit = 0;
            for (int i = 0; i <= 9; i++)
            {
                  bool check = (bool)(mask & (1 << i));
                  if (check) distinctdigit++, maxdigit = i;
            }
            return maxdigit == distinctdigit;
      }
      ll &ret = dp[pos][mask];
      bool &mem = memoize[pos][mask];
      if (!small && take && mem) return ret;
      int loop = 9;
      if (small) loop = a[pos];
      ll sum = 0;
      for (int i = 0; i <= loop; i++)
      {
            if (!take && i == 0) sum += solvedp(pos-1, 0, 0, 0);
            else sum += solvedp(pos-1, mask | (1 << i), small && i == a[pos], 1);
      }
      if (take && !small) mem = 1, ret = sum;
      return sum;
}
 
inline ll solve(ll x)
{
	int len = 0;
	while (x)
      {
            a[len++] = x % 10;
            x /= 10;
      }
	return solvedp(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++)
	{
		ll num;
		scanf("%lld", &num);
		printf("%lld\n", solve(num));
	}
	return 0;
}