【UVA-11651】Krypton Number System

【UVA-11651】Krypton Number System

通过矩阵快速幂转移状态

问题链接:https://vjudge.net/problem/UVA-11651

Solution:

首先关注到,对于每一种数字组合,可以都可以对应到一种确定的score值,而每一个score可以由多种数组组合得到。

最简单的考虑,自然是枚举数字组合,也就是搜索的办法,由于两个相邻数最小间隔为1,所以这个数字组合最长可能是S+1长度的,每个位置有B种选择,所以枚举的复杂度是\(O(TB^S)\)【其中T是数据组数】。这样显然无法在规定时间内跑完。

于是,我们从另一个角度——score的方面来考虑,注意到对于每一个score值,它的结尾数字只有B种,而转移到下一个score值仅与上一个score值相关,只需要对于每一种结尾枚举其下一个可能结尾就好,那么显然有:

\(dp[i][k] = \sum dp[i – (j – k)^2][j]\)

我们就可以使用动态规划来解决这个问题,对于每一个score值,我们需要枚举其B种结尾,对于每一种结尾,我们枚举下一个可能的结尾进行转移,因此复杂度是\(O(TSB^2)\)。十分可惜的是,这样依旧会TLE,还需要进一步优化。

这时注意到,对于单次转移,最远只能从第i行转移到\(i+(b – 1)^2\)行,也就是说,转移的方式是固定的,如果将dp数组的前\((b – 1)^2 – 1\)行构造成一个一维向量【把二维数组中的元素从左到右,从上到下依次排下来就好】,我们就可以通过写出一个\((b- 1) ^ 2 * b\)转移矩阵,得到任意位置的dp数组数据,具体点来说,如果对0到\((b – 1)^2 – 1\)dp数据乘一次转移矩阵,就得到1到\((b – 2)^2\)的dp数据。我们使用矩阵快速幂来先对变换矩阵进行计算。复杂度\(O(TB^9logS)\),虽然其中B的次数增高了,但是本题中数值很大的S变成了logS。

另外,由于转移矩阵十分稀疏【中间存在很多0】,我们需要调整一下矩阵乘法的顺序,并且先判断其中一边的值是否为0,再决定是否要相乘,可以节省很多时间。

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;
const LL MOD = 1ll << 32;
const int LIM = 250;
struct Matrix {
    LL v[LIM][LIM];
    int size;
    Matrix operator * (const Matrix & m) const {
        Matrix ret = {0};
        ret.size = size;
        for (int i = 0; i < size; i++) {
            for (int k = 0; k < size; k++) {
                if (v[i][k]) {
                    for (int j = 0; j < size; j++) {
                        ret.v[i][j] = (ret.v[i][j] + v[i][k] * m.v[k][j]) % MOD;
                    }
                }
            }
        }
        return ret;
    }
};
int b;
LL s, ans;
LL dp[LIM][LIM];

inline void init() {
    memset(dp, 0, sizeof dp);
    ans = 0;
    int lim = (b - 1) * (b - 1);
    for (int j = 1; j < b; j++) dp[0][j] = 1;
    for (int i = 0; i <= lim; i++) {
        for (int j = 0; j < b; j++) {
            for (int k = 0; k < b; k++) {
                if (j == k) continue;
                int tmp = (j - k) * (j - k);
                if (i + tmp > lim) continue;
                dp[i + tmp][k] += dp[i][j];
            }
        }
    }
}

Matrix buildBase() {
    Matrix ret = {{0}};
    ret.size = (b - 1) * (b - 1) * b;
    LL tmp;
    for (int i = 0; i <= ret.size - b; i++)
        ret.v[i][i + b] = 1;
    int lim = (b - 1) * (b - 1);
    for (int i = 0; i < lim; i++) {
        for (int j = 0; j < b; j++) {
            for (int k = 0; k < b; k++) {
                if (j == k) continue;
                tmp = i + (k - j) * (k - j);
                if (tmp == lim) ret.v[(tmp - 1) * b + k][i * b + j] = 1;
            }
        }
    }
    return ret;
}

Matrix powMod(int pow, Matrix m) {
    Matrix ret = {{0}};
    ret.size = m.size;
    for (int i = 0; i < ret.size; i++) ret.v[i][i] = 1;
    while (pow) {
        if (pow & 1) {
            ret = m * ret;
        }
        if (pow) m = m * m;
        pow >>= 1;
    }
    return ret;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    for (int k = 1; k <= t; k++) {
        cin >> b >> s;
        init();
        int lim = (b - 1) * (b - 1);
        if (s <= lim) {
            for (int j = 0; j < b; j++) ans += dp[s][j];
            cout << "Case " << k << ": " << ans << "\n";
        } else {
            Matrix base = buildBase();
            int size = lim * b;
            int pos = (lim - 1) * b;
            base = powMod(s - lim, base);
            for (int j = 0; j < b; j++) {
                LL tmp = 0;
                for (int k = 0; k < size; k++)
                    tmp = (tmp + base.v[pos + j][k] * dp[k / b + 1][k % b]) % MOD;
                ans = (ans + tmp + MOD) % MOD;
            }
            cout << "Case " << k << ": " << ans << "\n";
        }
    }
    return 0;
}