矩阵乘法(快速幂)结合dp结合除法逆元的例题

https://atcoder.jp/contests/abc271/tasks/abc271_g

题目的思路为：

构建dp矩阵，dp[i][j][k]表示开始前停在j，结束后停在k，且停下时恰好出现2^i次访问的概率

则dp[i]=dp[i-1]*dp[i-1]

(矩阵乘法的中间过程模拟的就是两个2^(i-1)次访问的中间停靠点，矩阵乘法中间的求和就是将不同中间过程的概率求和)

然后可以用快速幂的形式，求解访问n次的概率矩阵。

注意到，除法逆元按直觉写即可，一般都可以得到正确的答案。

代码：

#include<bits/stdc++.h>
using namespace std;
using LL = long long;

#define fore(x,y,z) for(LL x=(y);x<=(z);x++)
#define forn(x,y,z) for(LL x=(y);x<(z);x++)
#define rofe(x,y,z) for(LL x=(y);x>=(z);x--)
#define rofn(x,y,z) for(LL x=(y);x>(z);x--)
#define fi first
#define se second
LL n;
int x, y;
const int N = 24;
LL base[N][N];
LL res[N][N];
string str;
LL MOD = 998244353;
void Mul(LL m1[N][N], LL m2[N][N])
{
    LL res[N][N] = { 0 };
    fore(i, 0, 23)
    {
        fore(j, 0, 23)
        {
            fore(k, 0, 23)
            {
                res[i][j] += m1[i][k] * m2[k][j];
                res[i][j] %= MOD;
            }
        }
    }
    fore(i, 0, 23)
    {
        fore(j, 0, 23)
        {
            m1[i][j] = res[i][j];
        }
    }
}
LL QuickExp(LL base, LL exp)
{
    LL res = 1;
    while (exp)
    {
        if (exp & 1)
        {
            res *= base;
            res %= MOD;
        }
        base *= base;
        base %= MOD;
        exp >>= 1;
    }
    return res;
}
LL Inv(LL num)
{
    return QuickExp(num, MOD - 2);
}
LL QuickExp()
{
    fore(i, 0, 23) res[i][i] = 1;
    fore(i, 0, 23)
    {
        fore(j, 0, 23)
        {
            LL tmp = 1;
            int k = i + 1;
            k %= 24;
            LL p = 1;
            while (1)
            {
                if (k == j)
                {
                    LL up;
                    if (str[k] == 'T') up = x;
                    else up = y;
                    LL down = 100;
                    p = p * up%MOD*Inv(down) % MOD;
                    break;
                }
                else
                {
                    LL up;
                    if (str[k] == 'T') up = 100 - x;
                    else up = 100 - y;
                    LL down = 100;
                    p = p * up%MOD*Inv(down) % MOD;
                }
                k++;
                k %= 24;
            }
            LL q = 1;
            fore(i, 0, 23)
            {
                LL up;
                if (str[i] == 'T') up = 100 - x;
                else up = 100 - y;
                LL down = 100;
                q = q * up%MOD*Inv(down) % MOD;
            }
            tmp = (p * Inv(1 - q) % MOD + MOD) % MOD;
            base[i][j] = tmp;
        }
    }
    while (n)
    {
        if (n & 1)
        {
            Mul(res, base);
        }
        Mul(base, base);
        n >>= 1;
    }
    LL ans = 0;
    fore(i, 0, 23)
    {
        if (str[i] == 'A')
        {
            ans += res[23][i];
            ans %= MOD;
        }
    }
    return ans;

}
int main()
{
    cin >> n >> x >> y;

    cin >> str;
    cout << QuickExp() << endl;
}