洛谷P4639 [SHOI2011] 编译优化 题解

题目链接：P4639 [SHOI2011] 编译优化

题意：

就像 PASCAL 语言和 C/C++ 语言一样， SH 语言也是一种编程语言。 SH 语言共有 $26$ 个寄存器，用大写拉丁字母 A, B, … , Z 表示。 SH 语言的程序中，第一行依次是这 $26$ 个寄存器的初始值，用空格分隔。程序的第二行起，每一行都是一条命令。 SH 语言有三种命令，如下表所示（在格式这一列中，用下划线代替实际语言中的一个空格）。

• ADD命令 格式：ADD_R1_R2 功能：将寄存器 R2 的值加到寄存器 R1 上。 限制：无。

• GOTO 命令 格式：IF _R_ < _I1_ GOTO _LINE_ I2 功能：如果寄存器 R 的值小于立即数 I1 ，则跳转至第 I2 （ $\ge 2$ ）行，否则继续执行下一行。限制：至多出现一次，且只可能出现在第 I2 行之后。

• PRINT 命令 格式：PRINT_R 功能：打印寄存器 R 的值。限制：出现且仅出现在最后一行。

现给定一个 SH 语言的程序，请输出 PRINT 命令打印的值。

输入格式：

每个输入文件都是一个 SH 语言的程序。输入文件保证：所有寄存器的初始值以及 GOTO 命令中出现的立即数，均为不超过 $2^{63}-1$ 的非负整数，但程序执行过程中寄存器的值不限于此。

输出格式：

每个输出文件只有一行，包含一个整数，即 PRINT 命令所打印的值。

说明/提示：

在每个测试点，如果您的输出与标准答案完全一致，您将能得到该测试点的全部分数；否则，您将在该测试点得 $0$ 分。

本题为提交答案题，所有的 $10$ 个输入文件 compiler1.in ~ compiler10.in 都已存放在题目背景的下载链接中。对于每个输入文件，您需要分别给出相应的输出文件 compiler1.out ~ compiler10.out。

注意：您只需提交输出文件而无需提交任何程序。

附件： link

光看这题面和奇怪的风格，还以为要手写编译器呢。

由于 GOTO 只会出现一次，所以我们只需要搞明白循环在干什么就行了。

注意到 ADD A B 出现多次等于 A += B * k ，然后这又只有 26 个字母，很容易想到矩阵快速幂。

因为矩阵快速幂里那个贡献矩阵中 $A_{ij}$ 的含义就是 $i$ 对 $j$ 的贡献，结合矩阵乘法其实也很好理解。

所以我们只需要写个矩阵快速幂跑一跑就好了，不过这题最好直接算出来每个幂，方便判断。

理论上来说这题是需要写高精度的，但是数据里面都没有爆 long long ，那也省得浪费时间了。

时间复杂度 $\mathcal{O}(26^3 \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(1e5 + 15))

char s[233];
struct mat
{
    int a[26][26];
    void clear() { memset(a, 0, sizeof(a)); }
    int* operator[](const int x) { return a[x]; }
    const int* operator[](const int x) const { return a[x]; }
    mat operator * (const mat &o)
    {
        static mat tmp; tmp.clear();
        rep(k, 0, 25) rep(i, 0, 25) rep(j, 0, 25)
            tmp[i][j] += a[i][k] * o[k][j];
        return tmp;
    }
} A, tmp, mp[99];
int id, ans, limit, to, x[N], y[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    rep(i, 0, 25) cin >> A[0][i];
    while(true)
    {
        cin >> s; static int tim = 1; ++tim;
        if(s[0] == 'P') { cin >> s; ans = s[0] - 'A'; break; }
        else if(s[0] == 'A')
        {
            cin >> s; x[tim] = s[0] - 'A';
            cin >> s; y[tim] = s[0] - 'A'; A[0][x[tim]] += A[0][y[tim]];
        }else if(s[0] == 'I')
        {
            cin >> s; id = s[0] - 'A';
            cin >> s >> limit >> s >> s >> to;
            rep(i, 0, 25) ++mp[0][i][i];
            rep(i, to, tim - 1) rep(j, 0, 25) mp[0][j][x[i]] += mp[0][j][y[i]];
            int mx = 1;
            for(; mx < 64; mx++)
            {
                mp[mx] = mp[mx - 1] * mp[mx - 1];
                tmp = A * mp[mx]; if(tmp[0][id] >= limit) break;
            }
            Rep(i, mx, 0) { tmp = A * mp[i]; if(tmp[0][id] < limit) A = tmp; }
            A = A * mp[0];
        }
    }
    cout << A[0][ans] << '\n';
    return 0;
}

不过这题既然是提交答案题，那就贴一下每组数据的答案吧

100
1000000000
1000000000000000925
428911
23323
288452
1000000531162
89442725
1000000000000000000
2828427128

---

参考文献：

[1] https://www.luogu.com.cn/article/dvuddf63