前言

今天学动态dp的时候发现了这么一个东西

补充定理

$max(a,min(b,c))=min(max(a,b),max(a,c))$

$min(a,max(b,c))=max(min(a,b), min(a,c))$

矩阵乘法

由于$A(AC)=(AA)C$，即矩阵乘法满足结合律，因此，对于某种变换$A$，变换$n$次后对应的变换矩阵为$A^n$，则结果为$A^nC$，其中$A^n$用矩阵快速幂解决

因此对于形似$dp[i][j]=\sum_{k=1}^{n}dp[i-1][k]\cdot G[k,j]$的题目我们可以用矩阵快速幂解决

魔改矩阵乘法

下面通过举例说明

假设现在要求$f[i][j]=min_{k=1}^{n}(f[i-1][k]+G[k,j])$

我们重新定义矩阵乘法的第$i$行$j$列元为$C[i,j]=min_{k=1}^b(A[i,k]+B[k,j])$

下面证明其满足结合律

$\begin{aligned} (( A B ) C )[i, j] &=\min^{c} _{l=1}\left(\min _{k=1}^{b}( A [i, k]+ B [k, l])+ C [l, j]\right) \\ &=\min^{b} _{k=1} \min^{c} _{l=1}( A [i, k]+ B [k, l]+ C [l, j]) \\ &=\min^{b} _{k=1}\left( A [i, k]+\min _{l=1}^{c}( B [k, l]+ C [l, j])\right) \\ &=( A ( B C ))[i, j] \end{aligned}$

因此可以用矩阵快速幂解决

注意，重新定义过后的矩阵乘法单位阵不一定是对角矩阵$I$

事实上，图论中的Flody最短路算法也可看作一种魔改版的矩阵乘法

例题

Height All the Same(Codeforces 630E)

不带魔改的矩阵乘法。

这题当时不会做，老想着用组合数做（事实上组合数可做，代码更短）。

当$n*m$为奇数时，显然所有组合都可行，结果为$(r-l+1)^{nm}$

下面讨论当$n*m$为偶数的情况，由题解可知当且仅当奇数格个数为偶数是可行。

记$O$为可取奇数的数量，$E$为可取偶数的数量

使用矩阵乘法：考虑$dp_{odd}[i]$代表$i$个格子中有奇数个奇数格（即格子中的数为奇数）的选法，$dp_{even}[i]$代表$i$个格子中有偶数个奇数格的选法，那么有

$dp_{odd}[i] = dp_{odd}[i-1] \cdot E + dp_{even}[i-1] \cdot O$

$dp_{even}[i] = dp_{even}[i-1] \cdot E + dp_{odd}[i-1] \cdot O$

$dp_{odd}[1]=O,dp_{even}[1]=E$

最终答案为$dp_{even}[nm]$

显然可以用矩阵乘法，矩阵快速幂可解！

AC代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll mod = 998244353;

struct matrix{
    ll val[2][2];
    matrix(){memset(val, 0, sizeof val);}
    matrix operator *(const matrix & m){
        matrix result;
        for(int i=0; i<2; i++){
            for(int j=0; j<2; j++){
                for(int k=0; k<2; k++)
                    result.val[i][j] = (result.val[i][j] + val[i][k] * m.val[k][j] % mod) % mod;
            }
        }
        return result;
    }
};

matrix qpow(matrix base, ll t){
    matrix result;
    result.val[0][0] = result.val[1][1] = 1;
    while(t){
        if(t & 1) result = result * base;
        t >>= 1;
        base = base * base;
    }
    return result;
}

ll qpow(ll base, ll t){
    ll ret = 1;
    while(t){
        if(t & 1) ret = ret * base % mod;
        t >>= 1;
        base = base * base % mod;
    }
    return ret;
}

signed main(){
    ll n, m, l, r;
    cin >> n >> m >> l >> r;
    if((n * m) & 1 == 1){
        cout << (qpow(r - l + 1, n * m) % mod) << endl;
    }else{
        ll odd = (r + 1) / 2 - l / 2;
        ll even = r / 2 - (l - 1) / 2;
        matrix base;
        base.val[0][0] = base.val[1][1] = even;
        base.val[0][1] = base.val[1][0] = odd;
        base = qpow(base, n * m - 1);
        ll ans = base.val[1][0] * odd %mod + base.val[1][1] * even % mod;
        cout << (ans % mod) << endl;
    }
}

参考资料

《矩阵乘法在信息学中的应用_余华程》