解題區/解題區 - UVa

UVa 11651 - Krypton Number System

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

  • 相鄰數字不可相同
  • 不可前導為 0
  • score 分數為任兩個相鄰位數相減平方的總和

請問在 base 下，指定 score 的數字有多少個。

Sample Input

1
2
3
2
6 1
5 5

Sample Output

1
2
Case 1: 9
Case 2: 80

Solution

首先，可以知道每一次增加的總數最多為 (base - 1) (base - 1)，因此我們的狀態紀錄之少要追溯到當前分數 n - (base - 1) (base - 1)。

然而由於 score 過大，不可直接著手 dp[score][tail_digit] 之類的 dp 計算。仍可以計算於 (base - 1) * (base - 1) 以下的情況。

接著，利用遞迴公式 (線性變換矩陣 ?)，每一項為 a[score][tail_digit]，而分數必須保留到當前 score - (base - 1) * (base - 1)，因此狀態將會有 (base - 1) * (base - 1) * base，也就是矩陣最大上限 5 * 5 * 6 = 150。

矩陣的部分，可以假想每一次在尾數多增加一個 digit 上去，而在初始項部分仍必須依靠 dp 去計算。矩陣快速乘法直接套用 D&C 在 O(n^3 log k) 完成，並且計算時，盡可能將無用的 0 忽略計算，否則很容易 TLE。

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <stdio.h> 
#include <string.h>
const unsigned long long mod = 1LLU<<32;
struct Matrix {
    unsigned long long v[150][150];
    int row, col; // row x col
    Matrix(int n, int m, long long a = 0) {
        memset(v, 0, sizeof(v));
        row = n, col = m;
        for(int i = 0; i < row && i < col; i++)
            v[i][i] = a;
    }
    Matrix operator*(const Matrix& x) const {
        Matrix ret(row, x.col);
        for(int i = 0; i < row; i++) {
            for(int k = 0; k < col; k++) {
                if (v[i][k])
                for(int j = 0; j < x.col; j++) {
                    ret.v[i][j] += v[i][k] * x.v[k][j],
                    ret.v[i][j] %= mod;
                }
            }
        }
        return ret;
    }
    Matrix operator^(const int& n) const {
        Matrix ret(row, col, 1), x = *this;
        int y = n;
        while(y) {
            if(y&1)	ret = ret * x;
            y = y>>1, x = x * x;
        }
        return ret;
    }
};
int main() {
    int testcase, cases = 0, base, score;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &base, &score);
        printf("Case %d: ", ++cases);
        int N = (base - 1) * (base - 1);
        
        unsigned long long dp[64][64] = {}; // [sum][tail_digit] = #way 
        for (int i = 0; i <= N; i++)
            dp[0][i] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < base; j++) {
                for (int k = 0; k < base; k++) {
                    int d = (j - k) * (j - k);
                    if (i + d > N || j == k)
                        continue;
                    dp[i+d][k] += dp[i][j];
                    dp[i+d][k] %= mod;
                }
            }
        }
        
        if (score <= N) {
            unsigned long long ret = 0;
            for (int i = 1; i < base; i++)
                ret = (ret + dp[score][i])%mod;
            printf("%llu\n", ret);
            continue;
        }
        int r, c;
        r = c = (base - 1) * (base - 1) * base;
        Matrix x(r, c), y(c, 1);
        for (int i = 1; i <= N; i++)
            for (int j = 0; j < base; j++)
                y.v[(i-1) * base+j][0] = dp[i][j];
        for (int i = base; i < r; i++)
            x.v[i - base][i] = 1;
        for (int i = 0; i < base; i++) {
            for (int j = 0; j < base; j++) {
                if (i == j)	continue;
                int d = N - (i - j) * (i - j);
                x.v[(N-1)*base + i][d*base + j] = 1;
            }
        }
//		puts("");
//		for (int i = 0; i < r; i++, puts(""))
//			for (int j = 0; j < c; j++)
//				printf("%lld ", x.v[i][j]);
//		for (int i = 0; i < c; i++, puts(""))
//				printf("%lld ", y.v[i][0]);
        Matrix z = (x ^ (score - N)) * y;
        unsigned long long ret = 0;
        for (int i = 1; i < base; i++)
            ret = (ret + z.v[(N-1) * base + i][0])%mod;
        printf("%llu\n", ret);
    }
    return 0;
}