石头游戏CH3401

石头游戏

思路

状态矩阵:

题目中的状态是一个 n ∗ m n*m n∗m的矩阵,而一般情况下矩阵快速幂要求用一维向量作为状态矩阵,所以就把这个状态拉成长度为 n ∗ m n*m n∗m的向量了

原矩阵的(i, j) 为状态矩阵中的 F [ ( i − 1 ) ∗ m + j ] F[(i-1)*m + j] F[(i−1)∗m+j],不妨令 n u m ( i , j ) = ( i − 1 ) ∗ m + j num(i, j) = (i-1)*m + j num(i,j)=(i−1)∗m+j。那么在状态矩阵中就是 F [ n u m ( i , j ) ] F[num(i, j)] F[num(i,j)]了。

另外,令 F [ 0 ] = 1 F[0] = 1 F[0]=1,作为常数1,方便转移出常数。

转移矩阵:

假设ch为原矩阵对应位置i, j对应时刻k的操作:

① 如果ch为"N",则 A k ( n u m ( i , j ) , n u m ( i − 1 , j ) ) = 1 A_k(num(i, j), num(i-1, j)) = 1 Ak​(num(i,j),num(i−1,j))=1; ch 为 “W”、“E”、"S"也是同理。被转移的位置判断一下是否合法。

② 如果ch为[0-9],则 A k ( 0 , n u m ( i , j ) ) = c h − ′ 0 ′ A_k(0, num(i, j)) = ch-'0' Ak​(0,num(i,j))=ch−′0′(加上数值), A k ( n u m ( i , j ) , n u m ( i , j ) ) = 1 A_k(num(i, j), num(i, j)) = 1 Ak​(num(i,j),num(i,j))=1(保留上个状态的值)

③ 保证 F [ 0 ] F[0] F[0]不变, A k ( 0 , 0 ) = 1 A_k(0, 0) = 1 Ak​(0,0)=1;

④ A k A_k Ak​的其它部分为0。

不同的时刻有不同的转移矩阵,但是由于[1-6]的最小公倍数为60(6为操作序列的最大长度),所以直接处理k = 0-59时刻的所有状态矩阵,然后分解t = q*60 + r(0 ≤ r < 60),

令 A = ∏ k = 0 59 A k , 则 F t = F 0 ∗ A q ∗ ∏ k = 0 r − 1 A k A=∏_ {k=0}^{59}A_k,则F_t=F_0∗A^q∗∏_{k=0}^{r-1}A_k A=∏k=059​Ak​,则Ft​=F0​∗Aq∗∏k=0r−1​Ak​。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_NM = 65;
int n, m, t, act;
string opt[10];
string acts[10];
///F为状态矩阵,A为转移矩阵,A[i][0][0] = 1
ll F[MAX_NM], A[60][MAX_NM][MAX_NM], AAA[MAX_NM][MAX_NM];
inline int num(int i, int j)
{
    return (i-1)*m + j;
}
void mul(ll f[MAX_NM], ll a[MAX_NM][MAX_NM])
{
    ll c[MAX_NM];
    memset(c, 0, sizeof c);
    for (int j = 0; j < MAX_NM; j++)
        for (int k = 0; k < MAX_NM; k++)
            c[j] += f[k] * a[k][j];
    memcpy(f, c, sizeof c);
}
void mulb(ll a[MAX_NM][MAX_NM], ll b[MAX_NM][MAX_NM])
{
    ll c[MAX_NM][MAX_NM];
    memset(c, 0, sizeof c);
    for (int i = 0; i < MAX_NM; i++)
        for (int j = 0; j < MAX_NM; j++)
            for (int k = 0; k < MAX_NM; k++)
                c[i][j] += a[i][k]*b[k][j];
    memcpy(a, c, sizeof c);
}
void mulself(ll a[MAX_NM][MAX_NM])
{
    ll c[MAX_NM][MAX_NM];
    memset(c, 0, sizeof c);
    for (int i = 0; i < MAX_NM; i++)
        for (int j = 0; j < MAX_NM; j++)
            for (int k = 0; k < MAX_NM; k++)
                c[i][j] += a[i][k]*a[k][j];
    memcpy(a, c, sizeof c);
}
void init()
{
    F[0] = 1;
    for (int k = 0; k < 60; k++)
    {
        A[k][0][0] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                ///找到格子(i, j)对应的操作序列编号
                int index = opt[i-1][j-1] - '0'; 
                ///找到对应操作序列在第K秒时候应该执行第几个字符
                int indey = k % acts[index].size();
                char ch = acts[index][indey];
                if (isupper(ch))
                {
                    switch (ch)
                    {
                        case 'N':
                            if (i-1 >= 1)
                                A[k][num(i, j)][num(i-1, j)] = 1; break;
                        case 'S':
                            if (i+1 <= n)
                                A[k][num(i, j)][num(i+1, j)] = 1; break;
                        case 'W':
                            if (j-1 >= 1)
                                A[k][num(i, j)][num(i, j-1)] = 1; break;
                        case 'E':
                            if (j+1 <= m)
                                A[k][num(i, j)][num(i, j+1)] = 1; break;
                        case 'D':
                            A[k][num(i, j)][num(i, j)] = 0;
                    }
                }
                if (isdigit(ch))
                {
                    A[k][num(i, j)][num(i, j)] = 1;
                    A[k][0][num(i, j)] = ch - '0';
                }
            }
        }
    }
    ///初始化为单位矩阵
    for (int i = 0; i < MAX_NM; i++)
        AAA[i][i] = 1;
    for (int k = 0; k < 60; k++)
        mulb(AAA, A[k]);
}
int main()
{
    cin >> n >> m >> t >> act;
    for (int i = 0; i < n; i++)
        cin >> opt[i];
    for (int i = 0; i < act; i++)
        cin >> acts[i];
    init();
    int q = t/60;
    int r = t%60;
    for (; q; q >>= 1)
    {
        if (q&1)
            mul(F, AAA);
        mulself(AAA);
    }
    for (int i = 0; i < r; i++)
        mul(F, A[i]);
    ll ans = 0;
    for (int i = 1; i < MAX_NM; i++)
        ans = max(ans, F[i]);
    cout << ans << endl;
    return 0;
}
上一篇:AUTOSAR架构中的配置文件


下一篇:WC2021 游记