NAQ 2022

B. Birthday Gift

数位dp + 矩阵快速幂优化 + 一个比较tricky的同余优化，卡时间

credit：学姐给我讲的思路和官方solution的思路 QwQ

我太菜了，脑子在构造矩阵那里卡住了（说明不要上课走神的时候想题，容易把自己带进不存在的沟里）。后面具体实现的时候不断地犯一些愚蠢错误（范围，条件，etc.）本来想 2250 * 2250 用小数据测试一下矩阵写得对不对，但是空间卡住了只能硬上最终解法。学长后来说是结构体里放数组的原因，看来要update一下板子了（

Prompt

• Construct an integer number that
  • has a digits
  • % 225 == b
  • adjacent digits not identical
• How many ways?

Constraints

• $1 \leq a \leq 10^{18}$
• $0\leq b< 225$

Reason

• naive: 数位dp，从个位开始构造
  • i = 当前数字多少位，j = 当前个位是几，k = 当前数字除以\(225\)的余数
  • 0 <= p <= 9 && p != j
  • dp[i+1][p][(k * 10 + p) % 225] += dp[i][j][k]
  • edge case: 注意 dp[0][0] = 1 但转移的时候不能从0开始转，因为0会变成leading zero
  • 问题：超大时
• better: 把转移方程变成矩阵，用矩阵快速幂加速
  • 问题：2250 * 2250 的矩阵乘法还是会超时
• final:
  • 注意到 \(225=25*9=lcm(25,9)\)，因此

\[b\equiv x\bmod 9\land b\equiv x\bmod 25 \leftrightarrow b\equiv x\bmod 225\]

• 而\(25\)的余数只和最后两位有关
• 所以我们只需要记录 k = 当前数字除以\(9\)的余数，再手动check一下最后两位除以\(25\)的余数就可以了，这样就变成 90 * 90 的矩阵乘法，可以接受

Solution

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>
using namespace std;

#define PII pair<int, int>
#define LL long long

const LL MOD = 1e9 + 7;
const int N = 90;
const int K = 9;

struct Matrix {
    LL a[N][N];

    Matrix() {
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                a[i][j] = 0;
    }

    void display() const {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                cout << a[i][j] << " ";
            cout << endl;
        }
    }

    inline Matrix operator*(const Matrix &b) const {
        Matrix res;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                for (int k = 0; k < N; ++k)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j]) % MOD;
        return res;
    }

    inline Matrix operator^(LL x) const {
        Matrix res, bas;
        for (int i = 0; i < N; ++i)
            res.a[i][i] = 1;
        for (int i = 0; i < N; ++i)
            for (int j = 0; j < N; ++j)
                bas.a[i][j] = a[i][j] % MOD;
        while (x) {
            if (x & 1)
                res = res * bas;
            bas = bas * bas;
            x >>= 1;
        }
        return res;
    }
};

void solve() {
    LL a, b;
    cin >> a >> b;

    vector<LL> init(N, 0);

    if (a < 2) {
        cout << (b < 10 ? 1 : 0) << endl;
        return;
    }

    for (int i = 1; i < 10; i++)
        init[(i % 9) * 10 + i] = 1;

    auto mat = Matrix();
    for (int j = 0; j < 10; j++)
        for (int k = 0; k < K; k++)
            for (int p = 0; p < 10; p++) {
                int q = (k * 10 + p) % K;
                if (j != p)
                    mat.a[q * 10 + p][k * 10 + j] += 1;
            }

    auto f = mat ^ (a - 2);
    // f.display();

    vector<LL> res(N, 0);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) {
            res[i] += f.a[i][j] * init[j];
            res[i] %= MOD;
        }

    LL s = 0;

    for (int j = 0; j < 10; j++)
        for (int p = 0; p < 10; p++) {
            if ((j * 10 + p) % 25 != b % 25 || j == p)
                continue;
            for (int k = 0; k < K; k++) {
                int q = (k * 10 + p) % K;
                if (q == b % K) {
                    s += res[k * 10 + j];
                    s %= MOD;
                }
            }
        }

    cout << s << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    solve();
    return 0;
}