백준 11616 - Digit Division

문제 링크: https://acmicpc.net/problem/11616 

11616번: Digit Division

---

문제를 요약해봅시다.

• 주어진 $n$자리의 수열을 분할해 부분 수열로 만들되, 모든 부분 수열이 나타내는 정수가 $m$으로 나누어 떨어지도록 나누는 경우의 수를 계산해야 합니다.
• 예를 들면, 수열 $1246$을 $2$로 나누어 떨어지게 만드는 방법은 $[12, 4, 6], [124, 6], [12, 46], [1246]$의 $4$가지입니다.

---

수열을 조건에 맞게 임의로 분할하여 만든 부분 수열들을 $s_1, s_2, ... , s_k$라 합시다. 이때 다음이 성립합니다.

• 모든 부분 수열 $s_1, s_2, ... , s_k$이 나타내는 자연수는 $m$으로 나누어 떨어집니다.
• 임의의 인접한 두 부분 수열 $s_i, s_{i + 1}$을 이어 붙인 부분수열 $s_i s_{i+1}$ 역시 $m$으로 나누어 떨어집니다.

 

2번째 성질이 성립하는 이유를 알아봅시다. 부분 수열 \(s_i\)가 나타내는 자연수의 값을 \(x_i\)라 하고, \(x_i\)의 자릿수를 \(d_i\)라 하겠습니다. 이때 이어 붙여서 생긴 부분 수열 \(s_i s_{i+1}\)이 나타내는 자연수의 값은 \(x_i \times 10^{d_i} + x_{i+1}\)이 됩니다.

그런데 \(x_i, x_{i + 1}\)이 모두 \(m\)으로 나누어 떨어지므로, \(x_i \times 10^{d_i} + x_{i+1}\)도 \(m\)으로 나누어 떨어집니다.

 

이 성질을 이용하면, 처음에 주어진 \(n\)자리의 순열을 \(m\)으로 나누어 떨어지는 최소 크기의 부분 수열들로 앞에서부터 분할한 뒤 분할의 개수를 세는 것으로 문제를 해결할 수 있습니다.

예제인 \([1246], m = 2\) 의 경우 \([12, 4, 6]\)으로 분할을 할 수 있고, \(12\)와 \(4\) 사이의 분할과 \(4\)와 \(6\) 사이의 분할, 합계 \(2\)번의 분할이 있습니다. 이때 이 \(2\)개의 분할 각각을 해도 되고 하지 않아도 되는데, 분할을 하지 않아도 위에서 다룬 2번째 성질 때문에 부분 수열이 \(m\)으로 나누어 떨어지기 때문입니다. 따라서, 분할의 개수를 \(p\)라 했을 때 \(2^p\)가 답이 됩니다.

 

우리가 분할해서 얻은 수열들을 이어 붙여 얻을 수 있는 부분 수열들이 아닌 것 중에도 \(m\)으로 나눠지는 것들이 있으나, 이것들을 선택하면 부분 수열들을 전부 다 \(m\)으로 나누어 떨어지게 만들 수가 없습니다. 이러한 부분 수열들은 앞에서부터 분할해서는 등장하지 않기 때문입니다.

 

마지막으로, 어떻게 분할해도 모든 부분 수열을 \(m\)으로 나누어 떨어지게 할 수 없다면 \(0\)을 출력해야 합니다. 사소한 예외이니 놓치지 않도록 합시다.

 

시간복잡도는..

• 수열의 모든 숫자들을 한 번씩 순회하며 부분 수열로 분할하므로 \(O(n)\)
• 분할의 개수 \(p\)를 세고 \(2^p\)를 구해야 하고, 분할의 최대 개수가 \(n - 1\)개이므로 \(O(p) = O(n)\), 분할 정복을 이용하여 거듭제곱을 최적화하면 \(O(\log n)\)

 

총 \(O(n + \log n) = O(n)\)입니다.

---

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

int main() {
    fastio;
    
    ll n, m;
    cin >> n >> m;
    
    string s;
    cin >> s;
    
    ll mod = 1e9 + 7;
    
    // 앞에서부터 수열을 분할합니다.
    ll partitions = 0;
    ll current_division = 0;
    for (int i = 0; i < n; i++) {
        ll x = s[i] - '0';
        ll value = x % m;
        
        // 현재 탐색하고 있는 부분 수열을 m으로 나눈 값을 계산합니다.
        current_division = (current_division * 10 + value) % m;
        
        // 만약 m으로 나눈 값이 0이라면, 분할을 발견한 것입니다.
        // 분할의 개수를 1 증가시킵니다.
        if (current_division == 0) {
            partitions++;
        }
    }
    
    if (current_division) {
    	// m으로 나누어 떨어지게 분할하는 것이 불가능하면 0을 출력합니다.
        cout << 0;
    }
    else {
    	// 마지막으로 경우의 수를 구합니다.
        ll k = partitions - 1;
        ll f = 2;
        ll result = 1;
        while (k) {
            if (k % 2) result = (result * f) % mod;
            f = (f * f) % mod;
            k /= 2;
        }
        cout << result;
    }
}