Light OJ - 1158 - Anagram Division Tutorial
Problem Description here
Problem:
এই প্রব্লেমে আমাকে একটি স্ট্রিং s দেয়া থাকবে এবং একটি পজিটিভ সংখ্যা d দেয়া থাকবে। বলতে হবে স্ট্রিং টির এমন কতটি পারমুটেশন সম্ভব যা d দ্বারা ডিভিজিবল।
Solution:
১) Constraint এর দিকে লক্ষ্য করলে দেখবে স্ট্রিং লেন্থ মাত্র ১০। বুঝতেই পারতেছো এটি মূলত বিটমাস্ক ডিপির একটি প্রব্লেম।
২) এই প্রব্লেমে আমার দুটি স্টেট নেয়া দরকার।
স্টেট-১ঃ এখন পর্যন্ত স্ট্রিং এর কোন কোন পজিশনের ডিজিট টি ব্যাবহার করেছি।
স্টেট-২ঃ এখন পর্যন্ত বানানো সংখ্যাটি কে d দ্বারা মড করলে মড ভ্যালু কত।
এখানে, মড ভ্যালু ক্যালকুলেট করবো কিভাবে? নিজে নিজে চিন্তা কর।
৩) আমি যদি সবগুলো ডিজিট ব্যাবহার করে ফেলি তাহলে রিকার্শন থামাতে হবে। যদি মড ভ্যালু ০ হয় তার মানে আমার বানানো সংখ্যাটি d দ্বারা বিভাজ্য তাই ১ রিটার্ন করবো। অন্যথায়, ০ রিটার্ন করবো। এটি হবে Base Case।
৪) সমস্যা কিন্তু এখনো সমাধান হয় নি! কম্বিনেটরিক্স এর সামান্য একটু কাজ বাকি আছে। আশা করি সেটি তুমি নিজেই পারবে।
বিটমাস্ক ডিপি সম্পর্কে ধারণা থাকলে এখন প্রব্লেমটি নিজে নিজে সলভ করার চেষ্টা কর। ব্যার্থ হলে কোড দেখে নিতে পারো।
| #include<bits/stdc++.h> | |
| #define CIN ios_base::sync_with_stdio(0);cin.tie(0); | |
| #define ms(a,b) memset(a,b,sizeof(a)) | |
| #define RUN_CASE(t,T) for(__typeof(t) t=1;t<=T;t++) | |
| using namespace std; | |
| bool Check(int mask,int pos) | |
| { | |
| return (bool)(mask & (1<<pos)); | |
| } | |
| int Set(int mask,int pos) | |
| { | |
| return mask = (mask | (1<<pos)); | |
| } | |
| int d,len,dp[1<<11][1002],fact[12],fre[12]; | |
| string s; | |
| int FuN(int mask,int mod) | |
| { | |
| int pos = __builtin_popcount(mask); | |
| if(pos >= len) | |
| return (mod == 0); | |
| if(dp[mask][mod] != -1) | |
| return dp[mask][mod]; | |
| int ret = 0; | |
| for(int i=0 ; i<len ; i++){ | |
| if(!Check(mask , i)){ | |
| int digit = (s[i] - '0'); | |
| ret += FuN(Set(mask , i) , (mod*10+digit)%d); | |
| } | |
| } | |
| return dp[mask][mod] = ret; | |
| } | |
| void Solve(int t) | |
| { | |
| int i,j,k,ans; | |
| cin>>s>>d; | |
| len = (int)s.size(); | |
| ms(dp , -1); | |
| ms(fre , 0); | |
| ans = FuN(0 , 0); | |
| for(i=0 ; i<len ; i++){ | |
| int digit = s[i]-'0'; | |
| fre[digit]++; | |
| } | |
| for(i=0 ; i<=9 ; i++){ | |
| ans /= fact[fre[i]]; | |
| } | |
| cout<<"Case "<<t<<": "<<ans<<endl; | |
| } | |
| void Factorial() | |
| { | |
| fact[0] = 1; | |
| for(int i=1 ; i<12 ; i++) | |
| fact[i] = (i * fact[i-1]); | |
| } | |
| int main() | |
| { | |
| CIN; | |
| int t,T; | |
| cin>>T; | |
| Factorial(); | |
| RUN_CASE(t,T) | |
| { | |
| Solve(t); | |
| } | |
| return 0; | |
| } | |
Comments
Post a Comment