AOJ - ZIMBABWE 웨브바짐

AOJ - ZIMBABWE

이거 예전에 종만북 볼 때 정말 어려웠던 문젠데, 다시 푸니 풀렸다.

약간 Digit DP라고 부르는 류의 연습 문제정도가 되는 수준이고, 추후에 Digit DP에 대해서도 이 블로그에도 글을 작성할 예정이다.

$dp[available][modular][less]$ 정도로 두고,

• available: 지금까지 사용한 숫자를 비트로 표현한 것
• modular: $m$ 으로 나눈 나머지를 계속 가져가는 것
• less: 이미 원본 숫자보다 작아졌는지를 검사하는 플래그

dp를 아름답게 돌리면 된다.

주의할 점은 수가 중복되지 않게 가능한 숫자들을 모두 정렬해두고 $i=0$ 이거나 마지막으로 현재 사용한 숫자가 지금 사용해볼 숫자보다 작을때만 자식 재귀함수를 호출해주는 것이다.

const ll mod = 1e9 + 7;  
inline ll md(ll x) { return md(mod, x); }  
  
int ten[17];  
  
// 지금 계란 가격 e  
// 최종 계란 가격은 m으로 나뉘어진다.  
// 최종 가격 계란은 0으로 시작할 수 있다.  
// 최종 계란 가격은 e보다 작아야 한다.  
int e, m, e_size;  
string e_string, e_sorted;  
inline int get_original_digit(int i) {  
   return e_string[i] - '0';  
}  
inline int get_sorted_digit(int i) {  
   return e_sorted[i] - '0';  
}  
  
int dp[1 << 16][22][2];  
  
int fn(int available, int r, int less) {  
   int cnt = __builtin_popcountll(available);  
   if (cnt == 0) return r == 0 && less;  
  
   int &ret = dp[available][r][less];  
   if (~ret) return ret;  
   ret = 0;  
  
   int last_used = -1;  
   for (int i = 0; i < e_size; i++) {  
      int original_digit = get_original_digit(e_size - cnt);  
      int cur_digit = get_sorted_digit(i);  
      if (cur_digit > last_used && ((1 << i) & available)) {  
         if (!less && cur_digit > original_digit) continue;  
         last_used = cur_digit;  
         ret = md(ret + fn(available & ~(1 << i),  
                           md(m, r + ten[cnt - 1] * cur_digit),  
                           less || (cur_digit < original_digit))  
         );  
      }  
   }  
  
   return ret;  
}  
  
void solve() {  
   memset(dp, -1, sizeof dp);  
   cin >> e >> m;  
   ten[0] = 1;  
   for (int i = 1; i <= 16; i++) ten[i] = ten[i - 1] * 10;  
  
   e_string = to_string(e);  
   e_sorted = e_string;  
   sort(all(e_sorted));  
   e_size = sz(to_string(e));  
   cout << fn((1 << e_size) - 1, 0, 0) << endl;  
}