백준24970 균형 수

작성일 | In

문제 링크

  • http://icpc.me/24970

사용 알고리즘

  • DP

풀이

수를 반으로 잘라서 앞부분과 뒷부분의 합이 같도록 만들어야 합니다. 즉, (앞부분 절반의 합을 $S$로 만드는 경우의 수)와 (뒷부분 절반의 합을 $S$로 만드는 경우의 수), 그리고 이 조건을 만족하는 수들의 합을 알고 있다면 이들을 활용해 정답을 계산할 수 있습니다.

$C(len, sum, start)$와 $S(len, sum, start)$를 각각 숫자 $len$개를 사용했을 때 합이 $sum$이고, 제일 처음에 사용한 숫자가 $start$인 경우의 수와 그러한 수들의 합으로 정의합시다. 앞부분 절반은 0으로 시작하면 안 되기 때문에 이를 판별하기 위해 $start$가 필요합니다. $a\cdots b$꼴의 수 맨 뒤에 $c$를 추가해서 $a\cdots bc$를 만드는 방식으로 상태 전이를 하면 $C$배열과 $S$배열을 모두 계산할 수 있습니다.

  • $C(0,0,0,0) = 1, S(0,0,0,0) = 0$
  • $0\leq i < 10$인 $i$에 대해, $C(1,i,i,i) = 1, S(1,i,i,i) = i$
  • $C(len,sum,a) \leftarrow C(len-1, sum-c, a)$
  • $S(len,sum,a) \leftarrow S(len-1,sum-c,a)\cdot 10 + C(len-1,sum-c,a)\cdot c$

이제 실제로 정답을 구해봅시다. $f(n)$을 길이가 $n$인 균형 수들의 합이라고 정의하면, $\sum_{i=1}^{N} f(i)$를 계산하면 됩니다.

$n$이 짝수라면 앞 $n/2$개의 숫자와 뒤 $n/2$개의 숫자의 합이 동일해야 합니다. 모든 $s$에 대해 아래 식을 더하면 됩니다.

  • $\sum_{i=1}^{9} S(n/2,s,i) \cdot \sum_{i=0}^{9} C(n/2,s,i) \cdot 10^{n/2}$
    • leading zero 없이 합이 $s$인 수들의 합 / 뒷부분으로 가능한 경우의 수 / 뒤에 숫자 $n/2$개 붙음
  • $\sum_{i=0}^{9} S(n/2,s,i) \cdot \sum_{i=1}^{9} C(n/2,s,i)$
    • 합이 $s$인 수들의 합 / 앞부분으로 가능한 경우의 수

$n$이 홀수라면 앞 $\lfloor n/2\rfloor$개의 숫자와 뒤 $\lfloor n/2\rfloor$개의 숫자의 합이 동일하고, 그 사이의 숫자 하나가 들어가야 합니다. 모든 $0 \leq s < 10\cdot\lfloor n/2\rfloor$에 대해 아래 식을 더하면 됩니다.

  • $\sum_{i=1}^{9} S(n/2,s,i) \cdot \sum_{i=0}^{9} C(n/2,s,i) \cdot 10 \cdot 10^{n/2+1}$
    • leading zero 없이 합이 $s$인 수들의 합 / 뒷부분으로 가능한 경우의 수 / 가운데 들어갈 수 있는 숫자 개수 / 뒤에 숫자 $\lfloor n/2\rfloor + 1$개 붙음
  • $\sum_{i=1}^{9} C(n/2,s,i) \cdot \sum_{i=0}^{9} C(n/2,s,i) \cdot 45 \cdot 10^{n/2}$
    • 앞부분으로 가능한 경우의 수 / 뒷부분으로 가능한 경우의 수 / 가운데 들어갈 수 있는 수들의 합 / 뒤에 숫자 $\lfloor n/2\rfloor$개 붙음
  • $\sum_{i=0}^{9} S(n/2,s,i) \cdot \sum_{i=1}^{9} C(n/2,s,i) \cdot 10$
    • 합이 $s$인 수들의 합 / 앞부분으로 가능한 경우의 수 / 가운데 들어갈 수 있는 숫자 개수

$C(len,sum,\ast)$의 합과 $S(len,sum,\ast)$의 합도 같이 전처리하면 빠르게 정답을 계산할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 14348907;

ll Mul(ll a) { return a % MOD; }
void Add(ll &a, const ll b) { a += b; if(a > MOD) a -= MOD; }
template<typename ... Args> ll Mul(ll a, Args ...b) { return a * Mul(b...) % MOD; }

ll P[55] = {1}; // P[i] = 10^i
ll C[51][500][10][10], S[51][500][10][10]; // count, sum : [len, digit_sum, start, end]
ll CS[51][500], CSZ[51][500];              // count, without leading zero : [len, digit_sum]
ll SS[51][500], SSZ[51][500];              //   sum, without leading zero : [len, digit_sum]

ll f(int len){
    ll res = 0;
    if(len == 1) return 45;
    if(len % 2 == 0){
        len /= 2;
        for(int i=0; i<len*10; i++){
            Add(res, Mul(SSZ[len][i], CS[len][i], P[len])); // XXX...
            Add(res, Mul(SS[len][i], CSZ[len][i]));         // ...XXX
        }
    }
    else{
        len /= 2;
        for(int i=0; i<len*10; i++){
            Add(res, Mul(SSZ[len][i], CS[len][i], 10, P[len+1])); // XXX....
            Add(res, Mul(CS[len][i], CSZ[len][i], 45, P[len+0])); // ...X...
            Add(res, Mul(SS[len][i], CSZ[len][i], 10));           // ....XXX
        }
    }
    return res;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    for(int i=1; i<55; i++) P[i] = P[i-1] * 10 % MOD;

    C[0][0][0][0] = CS[0][0] = 1;
    for(int i=0; i<10; i++){
        C[1][i][i][i] = CS[1][i] = CSZ[1][i] = 1;
        S[1][i][i][i] = SS[1][i] = SSZ[1][i] = i;
    }
    CSZ[1][0] = 0;
    for(int i=2; i<=50; i++){
        for(int j=0; j<i*10; j++){
            for(int a=0; a<10; a++){
                for(int b=0; b<10; b++){
                    for(int c=0; c<10; c++){
                        C[i][j][a][b] += C[i-1][j-b][a][c];
                        S[i][j][a][b] += S[i-1][j-b][a][c] * 10 + C[i-1][j-b][a][c] * b;
                        C[i][j][a][b] %= MOD;
                        S[i][j][a][b] %= MOD;
                    }
                    Add(CS[i][j], C[i][j][a][b]);
                    Add(SS[i][j], S[i][j][a][b]);
                    if(a) Add(CSZ[i][j], C[i][j][a][b]);
                    if(a) Add(SSZ[i][j], S[i][j][a][b]);
                }
            }
        }
    }

    ll N, R = 0; cin >> N;
    for(int i=1; i<=N; i++) Add(R, f(i));
    cout << R;
}