【題解】TOJ 639. Hello, Weird Music Sheet!

題意

給定 \(n\)，求有多少種 \(a\) 使 \(a_1 \le a_2 \ge a_3 \le a_4 ...a_n\) 且 \(0 \le a_i \le 11\)。

\(n \le 10^{18}\)

觀察

可以考慮 DP，設 \(dp[i][j]\) 為當 \(a_{i+1} = j\)，\(a_1 \ldots a_i\) 有多少種可能性
轉移：

\[ dp_{i,j} = \begin{cases} \begin{aligned} &dp_{i-1,0} + \ldots + dp_{i-1,j} & \text{if } j \equiv 1 \mod{2}\\ &dp_{i-1,j} + \ldots + dp_{i-1,11} & \text{else} \end{aligned} \end{cases} \]

\(n\) 很大想到可以用矩陣快速冪
奇數->偶數和偶數->奇數的轉移式不同

作法

把 \(dp_{i,0}\) 到 \(dp_{i,11}\) 合起來，再考慮線性遞迴： \[ D_i = \begin{bmatrix} dp_{i,0} & dp_{i,1} & dp_{i,2} & \ldots & dp_{i,11} \end{bmatrix} \]

可以得到偶數項到奇數項的轉移矩陣為：

\[ A_1 = \begin{bmatrix} 1 & 1 & 1 & \ldots & 1\\ 0 & 1 & 1 & \ldots & 1\\ 0 & 0 & 1 & \ldots & 1\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 0 & 0 & 0 & \ldots & 1 \end{bmatrix} \]

奇數項到偶數項的轉移矩陣：

\[ A_2 = \begin{bmatrix} 1 & 0 & 0 & \ldots & 0\\ 1 & 1 & 0 & \ldots & 0\\ 1 & 1 & 1 & \ldots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ 1 & 1 & 1 & \ldots & 1 \end{bmatrix} \]

則當 \(n\) 為偶數： \[ \begin{aligned} D_n & = D_0 \times A_1 \times A_2 \times \ldots \times A_2\\ & = D_0 \times (A_1 \times A_2)^{\frac{n}{2}} \end{aligned} \]

否則： \[ \begin{aligned} D_n & = D_0 \times A_1 \times A_2 \times \ldots \times A_1 \\ & = D_0 \times (A_1 \times A_2)^{\lfloor \frac{n}{2} \rfloor} \times A_1 \end{aligned} \]

這樣我們就能矩陣快速冪了。

這邊附上矩陣快速冪的模板：

struct mat{
    vector<vector<int>> v;
    mat(){
        v.resize(N,vector<int>(N));
    }
    mat operator * (mat y){
        mat res;
        for (int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                for (int k=0; k<N; k++){
                    res.v[i][j] += v[i][k]*y.v[k][j];
                }
            }
        }
        return res;
    }
} I;

mat qpow (mat x, int y){
    mat res = I;
    for (; y; y>>=1,x=x*x){
        if (y&1){
            res = res*x;
        }
    }
    return res;
}

AC Code

const int N = 12, M = 1e9+7;

struct mat{
    vector<vector<int>> v;
    mat(){
        v.resize(N,vector<int>(N));
    }
    mat operator * (mat y){
        mat res;
        for (int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                for (int k=0; k<N; k++){
                    res.v[i][j] += v[i][k]*y.v[k][j];
                    res.v[i][j] %= M;
                }
            }
        }
        return res;
    }
} A1, A2, D0, I;

mat qpow (mat x, int y){
    mat res = I;
    for (; y; y>>=1,x=x*x){
        if (y&1){
            res = res*x;
        }
    }
    return res;
}

int n;

signed main(){
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            A1.v[i][j] = (j>=i);
            A2.v[i][j] = (j<=i);
        }
    }
    for (int i=0; i<N; i++){
        I.v[i][i] = 1;
        D0.v[0][i] = 1;
    }
    cin >> n;
    mat trans = qpow(A1*A2,n/2);
    if (n&1) D0 = D0*trans*A1, cout << D0.v[0][11] << '\n';
    else D0 = D0*trans, cout << D0.v[0][0] << '\n';
}