Lightoj-1021 Painful Bases

L
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; }
Code language: PHP (php)

About the author

Sheikh Arman Hossain
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments

আবু রিফাত মুহাম্মদ

সখের বশে প্রোগ্রামিং করি। নতুন নতুন জিনিস শিখতে এবং শেখাতে ভালবাসি।

যোগাযোগ করুন

error: Alert: Content is protected !!