「HDU 5015」233 Matrix

    「HDU 5015」233 Matrix

    HDU 5015

    给一个矩阵 aa。对于第一行,有 a0,1=233a_{0, 1} = 233,a0,2=2333a_{0, 2} = 2333,a0,3=23333a_{0,3} = 23333,…\dots。

    对于 ∀i,j≠0\forall i, j \neq 0,有

    ai,j=ai−1,j+ai,j−1a_{i,j} = a_{i-1, j} + a_{i, j - 1}

    给出 a1,0,a2,0,…,an,0a_{1, 0}, a_{2, 0}, \dots, a_{n, 0},请求出 an,ma_{n, m}。

    数据范围:1≤n≤101 \leq n \leq 10,1≤m≤1091 \leq m \leq 10^9。

    时空限制:11s / 6464MiB。

    Solution

    不妨设 a0,0=23a_{0,0} = 23。

    对 ai,j=ai−1,j+ai,j−1a_{i, j} = a_{i - 1, j} + a_{i, j - 1} 进行转换:

    ai,j=∑k=1iak,j−1+a0,ja_{i, j} = \sum\limits_{k = 1}^{i} a_{k, j - 1} + a_{0, j}

    特别地:

    a0,j=10×a0,j−1+3a_{0, j} = 10 \times a_{0, j - 1} + 3

    则有:

    ai,j=∑k=1iak,j−1+10×a0,j−1+3a_{i, j} = \sum\limits_{k = 1}^{i} a_{k, j - 1} + 10 \times a_{0, j - 1} + 3

    观察上式,注意到第 jj 列每个位置上的值都可以由第 j−1j - 1 列的若干个项递推而来。
    又注意到 n≤10n \leq 10,m≤109m \leq 10^9,于是考虑矩阵乘法加速递推。

    设 F(j)=(a0,ja1,j⋯an,j3)F(j) = \begin{pmatrix} a_{0, j} & a_{1, j} & \cdots & a_{n, j} & 3 \end{pmatrix},则有:

    F(j)=F(j−1)×(101010⋯100011⋯10001⋯10⋮⋮⋮⋱⋮⋮000⋯10111⋯11)F(j) = F(j - 1) \times \begin{pmatrix} 10 & 10 & 10 & \cdots & 10 & 0 \\ 0 & 1 & 1 & \cdots & 1 & 0 \\ 0 & 0 & 1 & \cdots & 1 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \\ 1 & 1 & 1 & \cdots & 1 & 1 \end{pmatrix}

    设转移矩阵为 GG,则 F(m)=F(0)×GmF(m) = F(0) \times G^m。

    时间复杂度 O(n3log⁡m)\mathcal{O}(n^3 \log m)。

    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    namespace IO {
        static char buf[1 << 20], *fs, *ft;
        inline char gc() {
            if (fs == ft) {
                ft = (fs = buf) + fread(buf, 1, 1 << 20, stdin);
                if (fs == ft) return EOF;
            }
            return *fs ++;
        }
        #define gc() getchar()
        inline int read() {
            int x = 0, f = 1; char s = gc();
            while (s < '0' || s > '9') {if (s == '-') f = -f; s = gc();}
            while (s >= '0' && s <= '9') {x = x * 10 + s - '0'; s = gc();}
            return x * f;
        }
    } using IO :: read;
    
    const int N = 110;
    
    const int mod = 1e7 + 7;
    
    int n, m;
    
    int f[N];
    
    int G[N][N];
    
    void mul(int d[N][N], int a[N][N], int b[N][N]) {
        static int c[N][N]; memset(c, 0, sizeof(c));
        for (int i = 0; i <= n + 1; i ++)
            for (int j = 0; j <= n + 1; j ++)
                for (int k = 0; k <= n + 1; k ++)
                    c[i][j] = (c[i][j] + 1ll * a[i][k] * b[k][j]) % mod;
        memcpy(d, c, sizeof(c));
    }
    
    void mulstar(int d[N], int a[N], int b[N][N]) {
        static int c[N]; memset(c, 0, sizeof(c));
        for (int j = 0; j <= n + 1; j ++)
            for (int k = 0; k <= n + 1; k ++)
                c[j] = (c[j] + 1ll * a[k] * b[k][j]) % mod;
        memcpy(d, c, sizeof(c));
    }
    
    void work() {
        f[0] = 23;
        for (int i = 1; i <= n; i ++) f[i] = read();
        f[n + 1] = 3;
    
        for (int j = 0; j <= n; j ++) {
            G[0][j] = 10;
    
            for (int i = 1; i <= n; i ++)
                if (i <= j) G[i][j] = 1;
                else G[i][j] = 0;
        } 
    
        for (int i = 0; i <= n; i ++)
            G[i][n + 1] = 0;
    
        for (int j = 0; j <= n + 1; j ++)
            G[n + 1][j] = 1;
    
        for (int b = m; b; b >>= 1) {
            if (b & 1) mulstar(f, f, G);
            mul(G, G, G);
        }
    
        printf("%d\n", f[n]);
    }
    
    int main() {
        while (scanf("%d%d", &n, &m) != EOF)    work();
    
        return 0; 
    }