(1086) 박성원

https://www.acmicpc.net/problem/1086

단계별로 풀어보기

40단계(동적 계획법 3) 4번째

 

 

 

dp[x][state]: 수열 중 고른 수를 비트로 나타낸 것을 state라 할 때, state상태에서 만들어진 나머지가 x인 수열에서 만들 수 있는 조건을 만족하는 수열의 경우의 수

이 값은 state가 완료된 상태일 때 x=0이면 1, 아니면 0이다.

이후로는 비스마스킹 DP와 재귀로 풀면 되는데, 수열이 정수형 범위를 넘어가므로 길이와 모듈러 값을 미리 전처리로 계산해둬야 한다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, k;
  
  cin >> n;
  
  vector<string> v0(n);
  vector<int> v(n), w(51);
  
  for(int i=0;i<n;i++)  cin >> v0[i];
  
  cin >> k;
  
  for(int i=0;i<n;i++){
    for(char c:v0[i])  v[i]= (v[i]*10+c-'0')%k;
  }
  
  w[0]= 1;
  for(int i=1;i<=50;i++)  w[i]= (w[i-1]*10)%k;
  
  vector dp(k, vector<long> (1<<n, -1));
  
  auto func= [&](auto self, int num, int state) -> long {
    if(state==(1<<n)-1)  return num==0;
    
    long &ret= dp[num][state];
    
    if(ret!=-1)  return ret;
    
    ret= 0;
    
    for(int i=0;i<n;i++){
      if(state&(1<<i))  continue;
      
      ret+= self(self, (num*w[v0[i].length()]+v[i])%k, state|(1<<i));
    }
    
    return ret;
  };
  
  long den= 1, cnt= func(func, 0, 0);
  for(int i=1;i<=n;i++)  den*= i;
  
  if(cnt==0){
    cout << "0/1";
  }else if(cnt==den){
    cout << "1/1";
  }else{
    pair<long,long> p= {cnt,den};
    
    while(p.second)  p= {p.second, p.first%p.second};
    
    cout << cnt/p.first << "/" << den/p.first;
  }
  
  return 0;
}