[LeetCode] 3272. Find the Count of Good Integers

https://leetcode.com/problems/find-the-count-of-good-integers/description/

BOJ - Find the Count of Good Integers

문제 유형: 조합론, 정수론, 수학, 브루트포스, 백트래킹, 비트마스킹

문제 난이도: Hard

 

문제

You are given two positive integers n and k.

An integer x is called k-palindromic if:

• x is a palindrome.
• x is divisible by k.

An integer is called good if its digits can be rearranged to form a k-palindromic integer. For example, for k = 2, 2020 can be rearranged to form the k-palindromic integer 2002, whereas 1010 cannot be rearranged to form a k-palindromic integer.

Return the count of good integers containing n digits.

Note that any integer must not have leading zeros, neither before nor after rearrangement. For example, 1010 cannot be rearranged to form 101.

 

양의정수 n과 k가 주어진다.

다음의 조건을 만족하는 정수 x는 k-팰린드로믹이라 한다:

• x는 팰린드롬이다
• x는 k의 배수이다

정수가 재배열되어 k-팰린드로믹 정수가 된다면, 좋은 정수라고 한다.

n자릿수의 좋은 정수의 개수를 구하시오.

 

풀이

대단한 방법은 없다. 그저 브루트 포스를 하는 것 뿐이다.

대신, 만들어질 수 있는 k-팰린드롬수들을 기반으로 경우의 수들을  중복을 고려하여 구성하면 된다.

ceil(n/2)길이의 반쪽을 구성하는 숫자 배열을 백트래킹으로 구성한다.

그리고 팰린드롬 수로 만들고, k로 나누어 떨어지는 것들만 추려서 배열에 담는다.

 

가능한 k-팰린드로믹 정수들이 구성되었다.

이 정수들 중, 준비들이 같은 경우가 있을 수 있다, 즉, 같은 정수가 여러 k-팰린드로믹 정수가 될 수 있으므로, 재료들의 집합으로 파싱하여 그것들로 재배치하는 경우의 수를 구할것이다.

long long의 정수 p를 하나 만들어서, digit i의 개수를 (4*i)만큼 우측쉬프트 하여 p에 OR연산하여 저장한다.

p >> (i*4) & 16을 하면, 역으로 꺼내올 수 있는 것이다.

long long형의 패턴들이 만들어졌다.

 

이제, 재배치될 수 있는 경우의 수를 구한다. (전체 경우의 수) - (0으로 시작하는 경우의 수)를 누적한다.

누적된 정답을 리턴한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

using ll = long long;

class Solution {
    int fact[11];

   public:
    void initFactorial() {
        fact[0] = 1;
        for (int i = 1; i <= 10; i++) {
            fact[i] = fact[i - 1] * i;
        }
    }
    void generate(int l, vector<int> &arr, vector<vector<int>> &res) {
        if (arr.size() == l) {
            vector<int> cpy(arr.begin(), arr.end());
            res.emplace_back(cpy);
            return;
        }
        for (int i = 0; i <= 9; i++) {
            arr.emplace_back(i);
            generate(l, arr, res);
            arr.pop_back();
        }
    }

    vector<vector<int>> getPalindromes(int n) {
        int l = n / 2 + n % 2;
        vector<vector<int>> res;
        vector<int> temp;
        for (int i = 1; i <= 9; i++) {
            temp.emplace_back(i);
            generate(l, temp, res);
            temp.pop_back();
        }
        return res;
    }

    vector<ll> getKPalindromes(int n, int k, vector<vector<int>> &palindromes) {
        unordered_set<ll> unique;

        for (const auto &half : palindromes) {
            int l = n / 2 + n % 2;
            if (half.size() != (unsigned)l) continue;
            ll full = 0;
            for (int i = 0; i < half.size(); i++) {
                full = full * 10 + half[i];
            }
            int start = (n % 2 == 1) ? (half.size() - 2) : (half.size() - 1);
            for (int i = start; i >= 0; i--) {
                full = full * 10 + half[i];
            }
            if (full % k == 0) {
                if (unique.find(full) == unique.end()) {
                    unique.insert(full);
                }
            }
        }
        vector<ll> res(unique.begin(), unique.end());
        return res;
    }

    ll getCount(int n, ll pat) {
        ll total = fact[n];

        for (int i = 0; i < 10; i++) {
            int f = (pat >> (i * 4)) & 15;
            total /= fact[f];
        }

        // Leading zero 제거
        ll invalid = 0;
        int zeroCount = (pat >> 0) & 15;
        if (zeroCount > 0) {
            ll temp = fact[n - 1];
            for (int i = 0; i < 10; i++) {
                int f = (pat >> (i * 4)) & 15;
                if (i == 0) f--;
                temp /= fact[f];
            }
            invalid = temp;
        }

        return total - invalid;
    }

    long long countGoodIntegers(int n, int k) {
        if (n == 1) {
            ll ans = 0;
            for (int i = 1; i <= 9; i++) {
                if (i % k == 0) ans++;
            }
            return ans;
        }
        initFactorial();
        vector<vector<int>> palindromes = getPalindromes(n);
        vector<ll> kPalindromes = getKPalindromes(n, k, palindromes);

        unordered_set<ll> patterns;
        for (ll kpal : kPalindromes) {
            vector<int> freq(10, 0);
            ll patternId = 0;
            ll x = kpal;
            while (x > 0) {
                freq[x % 10]++;
                x /= 10;
            }
            for (int i = 0; i < 10; i++) {
                patternId |= (1LL * freq[i] << (i * 4));
            }
            patterns.insert(patternId);
        }

        ll ans = 0;
        for (ll pat : patterns) {
            ans += getCount(n, pat);
        }
        return ans;
    }
};

 

Go

type Solver struct {
	fact [11]int64
}

func (s *Solver) initFactorial() {
	s.fact[0] = 1
	for i := 1; i <= 10; i++ {
		s.fact[i] = s.fact[i-1] * int64(i)
	}
}
func (s *Solver) generate(l int, arr []int, res *[][]int) {
	if len(arr) == l {
		cpy := make([]int, l)
		copy(cpy, arr)
		*res = append(*res, cpy)
		return
	}
	for i := 0; i <= 9; i++ {
		s.generate(l, append(arr, i), res)
	}
}

func (s *Solver) getPalindromes(n int) [][]int {
	l := n/2 + n%2
	var res [][]int
	for i := 1; i <= 9; i++ {
		s.generate(l, []int{i}, &res)
	}
	return res
}

func (s *Solver) getKPalindromes(n, k int, pals [][]int) []int64 {
	unique := make(map[int64]struct{})
	for _, half := range pals {
		l := n/2 + n%2
		if len(half) != l {
			continue
		}
		var full int64 = 0
		for _, d := range half {
			full = full*10 + int64(d)
		}
		start := len(half) - 1
		if n%2 == 1 {
			start--
		}
		for i := start; i >= 0; i-- {
			full = full*10 + int64(half[i])
		}
		if full%int64(k) == 0 {
			unique[full] = struct{}{}
		}
	}
	var res []int64
	for num := range unique {
		res = append(res, num)
	}
	return res
}
func (s *Solver) getCount(n int, pat int64) int64 {
	total := s.fact[n]
	for i := 0; i < 10; i++ {
		freq := (pat >> (i * 4)) & 15
		total /= s.fact[freq]
	}

	zeroCount := (pat >> 0) & 15
	if zeroCount == 0 {
		return total
	}

	invalid := s.fact[n-1]
	for i := 0; i < 10; i++ {
		freq := (pat >> (i * 4)) & 15
		if i == 0 {
			freq--
		}
		invalid /= s.fact[freq]
	}
	return total - invalid
}


func countGoodIntegers(n int, k int) int64 {
	if n == 1 {
		var ans int64 = 0
		for i := 1; i <= 9; i++ {
			if i%k == 0 {
				ans++
			}
		}
		return ans
	}

	s := Solver{}
	s.initFactorial()
	pals := s.getPalindromes(n)
	kpals := s.getKPalindromes(n, k, pals)

	patterns := make(map[int64]struct{})
	for _, val := range kpals {
		var pat int64 = 0
		count := [10]int{}
		for x := val; x > 0; x /= 10 {
			count[x%10]++
		}
		for i := 0; i < 10; i++ {
			pat |= int64(count[i]) << (i * 4)
		}
		patterns[pat] = struct{}{}
	}

	var ans int64 = 0
	for pat := range patterns {
		ans += s.getCount(n, pat)
	}
	return ans
}