글 읽기 - 사.. 살려주세요...

akswnd98 4년 전 0

요즘 반례를 못찾겠는 문제가 많네요...

#include <bits/stdc++.h>
using namespace std;

long long gcd(int a, int b) {
    if(a < b) swap(a, b);
    if(!(a % b)) return b;
    return gcd(b, a % b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    long long N, K, i, j, k, l, len_tmp[30], *len, mod[30], **dp; // len_tmp[N], len[1 << N], dp[1 << N][K], mod[N]
    long long dec[10000]; // dec[sum of len_tmp]
    char ar[30][100]; // ar[N][max of len_tmp]

    cin >> N;
    for(i = 0; i < N; i++) cin >> ar[i];
    cin >> K;
    if(K == 1) {
        cout << "1/1\n";
        return 0;
    }
    len = new long long[1 << N];
    dp = new long long*[1 << N];
    for(i = 0; i < 1 << N; i++) {
        dp[i] = new long long[K];
        fill_n(dp[i], K, 0);
    }
    fill_n(mod, N, 0);
    dec[0] = 1;
    for(i = 0; i < 9999; i++) dec[i + 1] = (dec[i] * 10) % K;
    for(i = 0; i < N; i++) {
        len_tmp[i] = strlen(ar[i]);
        for(j = len_tmp[i] - 1, k = 1; j >= 0; j--, k *= 10, k %= K) {
            mod[i] += k * (long long)(ar[i][j] - '0');
            mod[i] %= K;
        }
    }
    for(i = 0; i < 1 << N; i++) {
        len[i] = 0;
        for(j = 0; j < N; j++) if((1 << j) & i) len[i] += len_tmp[j];
    }
    dp[0][0] = 1;
    for(i = 0; i < N; i++) {
        for(j = 0; j < 1 << N; j++) {
            long long num = 0;
            for(k = 0; k < N; k++) num += ((1 << k) & j) ? 1 : 0;
            if(num != i) continue;
            for(k = 0; k < N; k++) {
                if((1 << k) & j) continue;
                for(l = 0; l < K; l++) {
                    dp[(1 << k) | j][(l + dec[len[j]] * mod[k]) % K] += dp[j][l];
                }
            }
        }
    }
    if(!dp[(1 << N) - 1][0]) {
        cout << "0/1\n";
        return 0;
    }
    long long perm = 1;
    for(i = N; i > 0; i--) perm *= i;
    cout << dp[(1 << N) - 1][0] / gcd(dp[(1 << N) - 1][0], perm) << '/' << perm / gcd(dp[(1 << N) - 1][0], perm)  << '\n';

    return 0;
}

akswnd98 4년 전 0

gcd 파라미터가 int형 이었네요...

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

사.. 살려주세요...

akswnd98 4년 전 0

akswnd98 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말