Wednesday, 08 December, 2021

Rifat's Blog

Competitive Programming Notebook

single post

  • Home
  • Lightoj-1021 Painful Bases
DP, LightOJ, Solve By OJ, Solve By Topic

Lightoj-1021 Painful Bases

Problem NamePainful Bases
JudgeLightoj
Problem Linkhttps://lightoj.com/problem/painful-bases
Algorithms & DSDynamic Programming , BitMasking
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define PB push_back
#define VST(V) sort(V.begin(),V.end())
#define VSTrev(V) sort(V.begin(),V.end(),greater<long long int>())
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
ll SET(ll NUM,ll POS)
{
    return NUM | (1<<POS);
}
bool isOn(ll NUM,ll POS)
{
    return (bool)(NUM & (1<<POS));
}
ll mem[1<<17][21];
ll base,k;
ll n;
vector<ll>V;
ll dp(ll mask,ll mod)
{
    if(mask==(1<<n)-1)
    {
        if(mod==0)
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    if(mem[mask][mod]!=-1)
    {
        return mem[mask][mod];
    }
    ll ans=0;
    for(ll i=0; i<n; i++)
    {
        if(isOn(mask,i)==0)
        {
            ll tm_mask=SET(mask,i);
            ll remainder=((mod*base)+V[i])%k;
            ans+=dp(tm_mask,remainder);
        }
    }
    return mem[mask][mod]=ans;
}
int main()
{
    map<char,ll>mp;
    for(ll i=0; i<10; i++)
    {
        char ch=i+'0';
        mp[ch]=i;
    }
    for(ll i=0; i<6; i++)
    {
        char ch=i+'A';
        mp[ch]=i+10;
    }
    //freopen("1input.txt","r",stdin);
    fast;
    ll tcase=1;
    cin>>tcase;
    for(ll test=1; test<=tcase; test++)
    {
        V.clear();
        cin>>base>>k;
        string s;
        cin>>s;
        n=s.size();
        for(ll i=0; i<n; i++)
        {
            V.PB(mp[s[i]]);
        }
        for(ll i=0; i<=(1<<n)+10; i++)
        {
            for(ll j=0; j<=k; j++)
            {
                mem[i][j]=-1;
            }
        }
        ll ans=dp(0,0);
        cout<<"Case "<<test<<": "<<ans<<"\n";
    }
    return 0;
}
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

Created by Abu Rifat Muhammed Al Hasib
2021 © All rights reserved


error: Alert: Content is protected !!