백준 11616 / C++

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

11616번: Digit Division

 

[ 풀이 ]

우선 짚고갈 것은 전체수가 m의 배수가 아니라면  m의 배수인 여러부분으로 분할할 수 없다. 

이제 전체수가 m의 배수라고 하자. 이제 앞에서부터 수를 만들어가면서 m의 배수가 되면 개수를 세어주자.

앞부분이 m의 배수이고, 전체수가 m의 배수이면 나머지도 m의 배수이기 때문이다. 

이렇게 센 개수가 나눌 수 있는 라인의 개수이다. 여기서 마지막 라인은 그냥 안센것과 같으므로 1개 빼주고.. 

이제 이 라인들을 결정할지 말지 2가지 선택이 있으므로 2^개수 가 답이 된다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, m, ret, cnt = -1;
const ll MOD = 1e9 + 7;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	while (n--) {
		char s; cin >> s;
		// 앞에서부터 수 만들기 
		ret = (10 * ret + (s - '0')) % m;
		if (ret == 0) cnt++;
	}
	// 전체수가 m의 배수 x
	if (ret) {
		cout << 0;
		return 0;
	}
	ll ans = 1;
	while (cnt--) {
		ans = (2 * ans) % MOD;
	}
	cout << ans;
}