백준 20932 약수 의식

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

20932번: 약수 의식

1,2,3,4의 카드가 있다고 해보자

 

1,2,3의 카드로 만들 수 있는 수는 

 

123

132

213

231

312

321

이렇게 6가지이다. 

 

이 다음에 4카드를 뽑았다고 하면 

 

1234

1324

2134

2314

3124

3214

 

이렇게 된다. 

 

따라서 우리는 4를 마지막으로 뽑았을때의 모든 경우에 대해서 가지고 있어야 마지막으로 4가 나왔을때의 나머지가 0인지 아닌지 확인할 수 있다. 

 

우리가 나머지를 구하는 만큼 우리는 나머지만 가지고 있으면 된다. 

왜냐 다음과 같은 MOD식이 성립하기 때문이다. 

 

(a*b)%M = (a%M * b%M)%M 

(a+b)%M = (a%M + b%M)%M 

 

dp식은 잘 짜보자. 

 

#include <bits/stdc++.h>
using namespace std;
#define MAX 150005
#define pii pair<int, int>
#define ll long long
#define pll pair<ll, ll>
#define INF 1e9
#define LINF 1e18
#define all(v) (v).begin(), (v).end()

ll num[16];
ll dp[1<<16][10][10];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    cout<<fixed;
    cout.precision(7);
    //cin >> tt;
    while(tt--) {
        int N;
        cin >> N;
        for(int i=0; i<N; i++)cin >> num[i];
        for(int j=0; j<N; j++){
            for(int a=1; a<=9; a++){
                dp[1<<j][a][num[j]%a] = 1;
            }
        }
        for(int i=0; i<=(1<<N)-1; i++){
            for(int j=0; j<N; j++){
                if(!((1<<j)&i))continue;
                for(int a=1; a<=9; a++){
                    for(int b=0; b<a; b++){
                        dp[i][a][(((b%a)*(10%a))%a + (num[j]%a))%a] += dp[i^(1<<j)][a][b];
                    }
                }
            }
        }
        double sum = 0;
        double total = 1;
        for(int i = 0; i < N; i++){
            sum += dp[(1<<N)-1 ^ (1<<i)][num[i]][0];
        }
        while(N){
            total *= N;
            N--;
        }
        cout << (1.0)*sum/total;
    }
}