백준 11616 Digit division

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

오랜만에 글을 작성하네요. 몸도 마음도 힘들었던 1달이라 알고리즘 문제를 풀 여력이 없었습니다.

결론부터 말하자면, 이 문제는 아이디어성 수학문제입니다. 우리는 숫자 n을 m으로 나누어지는 블록의 집합으로 나눌 수 있습니다.

n이 m으로 나누어지지 않는다면 n은 “m의 배수인 블록”들을 연결하여 만들 수 없음은 자명합니다.

이제 문제는 블록 x개를 순서를 바꾸지 않고 그룹화하는 개수를 묻는 문제로 바뀌었습니다.

따라서, $ 2^{x-1} $ 개가 정답입니다.

#include<bits/stdc++.h>
using namespace std;
const int MD=1e9+7;
const int SZ=300005;
int rem[SZ];
string s;
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,m; cin>>n>>m;
    cin>>s;
    rem[0]=(s[0]-'0')%m;
    for(int i=1;i<n;i++) rem[i]=(rem[i-1]*10+s[i]-'0')%m;
    if(rem[n-1]!=0){
        cout<<0;
        return 0;
    }
    int xx=0;
    for(int i=0;i<n;i++){
        if(rem[i]==0) xx++;
    }
    xx--;
    int ans=1;
    while(xx--){
        ans=(ans*2)%MD;
    }
    cout<<ans;
    return 0;
}