[JOI 2012 예선] ジグザグ数(지그재그 숫자) ★

문제 링크

질문은 언제나 환영입니다.

풀이

지그재그의 조건을 생각해보자.

지그재그는 인접합 2~3개 정도의 원소만 보면 된다. 지그 다음에는 재그 그 다음에는 지그...

따라서 지그 또는 재그의 상태끼리 다 묶어서 관리하면 계산량이 $10^{500}$ 가까이에서 훅 줄어서 reasonable해 질 것이다.

 

그리고 지그와 재그를 표현함에 있어서 그 자리의 숫자들도 당연히 관리해야 할 것이다.

지그/재그 상태와 자리 숫자가 같아도 몇 자릿수인지에 따라 달라질 것이다. 그래서 자릿수도 관리하고...

 

$M$의 배수라고 하니까, 좀 고민하다가 보면 $M$으로 나눈 나머지를 잘 써주면 좋겠다 싶은데, 이 정보도 함께 관리하면 되겠다.

 

$U(i,j,k):=i$자리에서 증가세로 숫자 $j$에 도달했을 때, 나머지가 $k$인 경우의 수

$D(i,j,k):=i$자리에서 감소세로 숫자 $j$에 도달했을 때, 나머지가 $k$인 경우의 수

라고 정의를 한 뒤에 자연스러운 전이 과정만 추가하면 된다.

 

사실 문제를 푸는 것은 P2 치고 상당히 쉽다.

그런데, 문자열로 관리하면서 자릿수 따지면서 DP 테이블에 초깃값 넣어주는 과정이 매우 힘들다.

아무튼 ㅅㄱ...

코드

구현하다가 숨 넘어갈 뻔 했다.

함수 f(v)의 끝자락 부분이 핵심이고, 나머지는 내가 구현을 너무 못했다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define all(x) (x).begin(), (x).end()
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)

const int MOD = 10000;
int m;
#define Add(x,y) x = add(x,y)
ll add(ll x, ll y) { return (x=(x+y)%MOD) >= 0 ? x : x+MOD; }

vector<int> input() {
    string x; cin >> x;
    vector<int> r;
    for (int i = siz(x)-1; i >= 0; --i) {
        r.push_back(x[i]-'0');
    }
    return r;
}

ll T[503] {1};
inline ll t(ll n, ll e) { // (n*10^e)%m
    return (n*T[e])%m;
}

const int N = 503;
bool h(vector<int> &v) {
    ll s = 0;
    for (int i = siz(v)-1; i >= 0; --i) {
        s = (s*10)%m;
        s = (s+v[i])%m;
    }
    return s == 0;
}
bool g(vector<int> &v) {
    if (siz(v) == 1) return v[0]%m == 0;
    if (v[0] == v[1]) return false;
    if (siz(v) == 2) return (10*v[1]+v[0])%m == 0;
    bool dic = v[0] > v[1];
    for (int i = 2; i < siz(v); ++i) {
        dic = !dic;
        if (dic) {
            if (v[i-1] <= v[i]) return false;
        } else {
            if (v[i-1] >= v[i]) return false;
        }
    }
    return h(v);
}

ll U[N][10][500] {0,}, D[N][10][500] {0,};
ll f(const vector<int> &v) { // calculate 1~'v'-1
    if (siz(v) == 1) return (v[0]-1)/m;
    fill(U[0][0],U[N-1][10],0), fill(D[0][0],D[N-1][10],0);
    int k = siz(v)-1;
    
    rep(i,1,v[k]-1) U[k][i][t(i,k)] = D[k][i][t(i,k)] = 1; // 맨 앞 자릿수가 다르고 더 작은 경우들
    rep(i,1,k-1) rep(j,1,9) U[i][j][t(j,i)] = D[i][j][t(j,i)] = 1; // 자릿수가 적은 애들(두 자릿수 이상)
    rep(j,1,9) U[0][j][j%m] = 1; // 한 자릿수는 U, D 중 U만 체크
    
    bool dic = v[k] > v[k-1];
    ll s = t(v[k],k);
    if (!dic) { // v[k] <= v[k-1]
        rep(j,0,v[k]-1)
            Add(D[k-1][j][(s+t(j,k-1))%m],1);
    }
    
    for (int i = k-1; i >= 0; --i) {
        if (dic) { // v[i+1] > v[i]일 차례
            rep(j,0,min(v[i]-1,v[i+1]-1)) {
                Add(D[i][j] [(s+t(j,i))%m],1);
            }
            if (v[i+1] <= v[i]) break;
        } else { // v[i+1] < v[i]일 차례
            rep(j,v[i+1]+1,v[i]-1) {
                Add(U[i][j] [(s+t(j,i))%m],1);
            }
            if (v[i+1] >= v[i]) break;
        }
        s = (s+t(v[i],i))%m;
        dic = !dic;
    }
    
    for (int i = k; i > 0; --i) {
        rep(j1,0,9) rep(p,0,m-1) {
            rep(j2,0,j1-1) {
                Add(D[i-1][j2][(p+t(j2,i-1))%m], U[i][j1][p]);
            }
            rep(j2,j1+1,9) {
                Add(U[i-1][j2][(p+t(j2,i-1))%m], D[i][j1][p]);
            }
        }
    }
    ll res = 0;
    rep(i,0,9) Add(res,U[0][i][0]+D[0][i][0]);
    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    vector<int> a = input(), b = input();
    cin >> m;
    rep(i,1,500) T[i] = (T[i-1]*10)%m;
    cout << add(f(b)+g(b),-f(a));
}