[BOJ] 백준 1086번: 박성원

주어진 수 K로 1~100 까지 수를 나눈 나머지를 dp배열에 저장하여 메모이제이션 탐색 

종만북에 비슷한 문제가 있음

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory.h>
using namespace std;

typedef long long ll;
ll n,k;
ll mod[16][101];
ll dp[100000][100]; // state에서 나머지 k인 경우
string arr[16];
ll ans =0;
ll gcd(ll a,ll b){
	ll c= a %b;
	while(c){
		a= b;
		b= c;
		c = a%b;
	}
	return b;
}
ll recv(ll state, ll m){
	if(state == (1<<n) - 1){
		return (m == 0);
	}
	ll &ret = dp[state][m];
	if(~ret) return ret;
	ret = 0;
	for(int i = 0 ; i < n ; i ++){
		if(state & (1 << i)){
			continue;
		}
		ll _m = mod[i][m];
		ret += recv(state | (1<<i), _m);
	}
	return ret;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i = 0 ;i <n ; i++){
		cin >> arr[i];
	}
	memset(dp,-1,sizeof(dp));
	cin >> k ;
	// j arr[i]  mod k =  mod[i][j] 
	for(ll i = 0 ; i < n ; i++){	
		int len = arr[i].length();
		for(ll j = 0 ; j <= k; j++){
			ll cnt = j % k ;
			for(int a = 0 ;a < len ; a ++){
				cnt = cnt * 10 + (arr[i][a] - '0');
				cnt %= k;
			}
			mod[i][j]  = cnt;
		}
	}
	ll re = recv(0,0);
	ll total = 1;
	for(ll i = n ; i > 0 ; i--){
		total *= i;
	}
	if(re == 0){
		cout << "0/1";
	}
	else{
		ll g = gcd(re,total);
		cout << re/g << "/" << total/g;
	}
}