3343 - Count Number of Balanced Permutations
정보
- 문제 보기: 3343 - Count Number of Balanced Permutations
- 소요 시간: 💥1시간 초과
- 풀이 언어:
java
- 체감 난이도: 5️⃣
- 리뷰 횟수: ✅
풀이 키워드
스포주의
DP
수학
조합론
풀이 코드
정보
- 메모리: 45300 KB
- 시간: 96 ms
class Solution {
final int MOD = 1_000_000_007;
int[] cnt = new int[10];
long[] fact = new long[81];
long[] inv = new long[81];
long[] invFact = new long[81];
int n, evenLen, oddLen, halfSum;
int[][][] memo;
private long dp(int i, int depth, int curSum) { // i: current digit | depth: length of selected
if (curSum > halfSum || depth > evenLen) return 0;
if (i > 9) return (depth == evenLen && curSum == halfSum) ? 1 : 0;
if (memo[i][depth][curSum] != -1) return memo[i][depth][curSum];
long res = 0;
for (int use = 0; use <= cnt[i] && depth+use <= evenLen && curSum+i*use <= halfSum; ++use) {
long evenPerm = fact[depth+use] * invFact[depth] % MOD * invFact[use] % MOD;
long oddInv = invFact[cnt[i]-use]; // 안쓴만큼 홀수 인덱스로 감 -> 홀수 인덱스 배치 수식의 분모
res = (res + (evenPerm * oddInv % MOD) * dp(i+1, depth+use, curSum+i*use)) % MOD;
}
memo[i][depth][curSum] = (int) res;
return res;
}
public int countBalancedPermutations(String num) {
n = num.length();
int totalSum = 0;
for (char ch : num.toCharArray()) {
totalSum += ch - '0';
++cnt[ch-'0'];
}
if ((totalSum & 1) == 1) return 0; // can't satisfy condition
halfSum = totalSum / 2;
evenLen = (n+1) / 2;
oddLen = n - evenLen;
memo = new int[10][evenLen+1][halfSum+1];
for (int i = 0; i < 10; ++i)
for (int j = 0; j <= evenLen; ++j)
Arrays.fill(memo[i][j], -1);
precalc();
long res = dp(0, 0, 0);
// 홀수 인덱스 배치 수식의 분자 곱하기
res = res * fact[oddLen] % MOD;
return (int) res;
}
public void precalc() {
fact[0] = inv[0] = invFact[0] = 1;
for (int i = 1; i < 81; ++i) fact[i] = fact[i-1] * i % MOD;
inv[1] = 1; // extended euclidean
for (int i = 2; i < 81; ++i) inv[i] = MOD - (MOD/i) * inv[MOD%i] % MOD;
for (int i = 1; i < 81; ++i) invFact[i] = invFact[i-1] * inv[i] % MOD;
}
}
풀이 해설
주어진 문자열의 숫자를 뒤섞어서 홀수 인덱스 합, 짝수 인덱스 합이 같도록 하는 경우의 수를 세는 문제이다.
경우의 수가 매우 많을 수 있어 모듈러 연산을 수행하며 중복순열 개수를 계산해야 하는데,
모듈러 연산 공식에 나눗셈은 정의되어있지 않으므로 모듈러 역원을 사용해야 한 다.
📌 모듈러 역원 구하기
모듈러 역원은 페르마의 소정리 or 확장 유클리드 호제법 중 선택하여 구현할 수 있고
만약 사전 계산하여 배열로 다 구해둘 목적이면 총 복잡도를 가진 페르마 소정리보단
재귀적으로 처리하는 확장 유클리드 호제법이 좀 더 나을 수 있겠다.
하지만 쓰이는 역원이 한정되어있기 때문에 퍼포먼스를 위해선 페르마로 가는게 나아보인다. ㅡ_ㅡ