卡奥蓓丝克 批

题意

写了一版解释，发现太形式化了。所以自己嘟题。

题解

计算部分

连续若干次赋值，本质上就是常系数齐次递推，可以用矩阵快速幂维护。

具体地，设所有元素为 $V_1, V_2, V_3, \cdots, V_n$，用列向量

$$X = \begin{bmatrix} 1 \\ V_1 \\ V_2 \\ V_3 \\ \vdots \\ V_n \\ \end{bmatrix}$$

维护所有元素的值。

考虑一个赋值 $\lambda$ ，不妨设其为 $V_1 \leftarrow V_2 + V_3 + V_2 + 114$，则可构造矩阵

$$T_{\lambda} = \begin{bmatrix} 1 & 0 & 0 & 0 & \cdots \\ 114 & 0 & 2 & 1 & \cdots \\ 0 & 0 & 1 & 0 & \cdots \\ 0 & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ \end{bmatrix}$$

表示之。

$X\leftarrow T_{\lambda} X$ 表示将 $\lambda$ 应用一次。

同一次循环内，赋值或次层循环的矩阵表示是可加的，设 $T = \sum T_{\lambda}$

循环 $k$ 次等价于对 $T$ 做 $k$ 次幂。

激动人心的 Parsing 部分

先 Tokenize。我设计了以下的 Token：

• EOL：行结束，在做单行的 Expression parsing 时的妙妙小工具；
• IDENTIFIER：标识符；
• LOOP_END：就是你想的那个意思；
• NUMBER，非负整数字面值；
• RETURN：就是你想的那个意思。

括号是可以忽略的，因为只有加法。

没有做 LOOP_BEGIN 的设计，因为行首的一个 NUMBER 一定是一个 MOO Loop。

然后发现不用更进一步了，给 Token 带一个整数表示一些附加信息，可以开始跑了。

遇到新的一层循环，进去递归地处理。

实现起来是非常简单且清晰地。

码

#include <iostream>
#include <map>
#include <sstream>
#include <string>
#include <vector>

#include <cassert>

namespace SLV {
#define qep(i, st, ed) for (int i = (st), _##i = (ed); i <  _##i; ++i)
using namespace std;
using u32 = unsigned int;
using u64 = unsigned long long;
using vu = vector<u32>;

constexpr u32 MOD = 1e9 + 7;

struct Mat {
   u32 n, m;
   vector<vu> a;

   Mat(u32 _n = 100, u32 _m = 100): n(_n), m(_m), a(n, vu(m)) {}
   
   vu &operator[](u32 i) { return a[i]; }
   const vu &operator[](u32 i) const { return a[i]; }

   void setI() {
      assert(n == m);
      qep(i, 0, n) a[i][i] = 1;
   }

   friend Mat operator*(const Mat &lhs, const Mat &rhs) {
      assert(lhs.m == rhs.n);
      Mat res(lhs.n, rhs.m);
      qep(i, 0, lhs.n) qep(k, 0, lhs.m) {
         const u64 r = lhs[i][k];
         qep(j, 0, rhs.m) res[i][j] = (res[i][j] + r * rhs[k][j]) % MOD;
      }
      return res;
   }

   friend Mat operator^(Mat &&a, u32 b) {
      assert(a.n == a.m);
      Mat res(a.n, a.m); res.setI();
      for (; b; b >>= 1, a = a * a) if (b & 1) res = res * a;
      return res;
   }
};

enum TokenType {
   BAD_TOKEN,
   EOL,
   IDENTIFIER, // Variable identifier.
   LOOP_END,
   NUMBER,     // Literal number, also means `LOOP_BEGIN'.
   RETURN
};

struct Token {
   TokenType type;
   u32 val; // Anythin' enclosed could be indicated by a u32 val.

   Token(TokenType _type = BAD_TOKEN, u32 _val = -1): type(_type), val(_val) {}
};

map<string, u32> idmp;
u32 idc;

template<typename INSTREAM>
Token nextToken(INSTREAM &stream) {
   if (string s; stream >> s) {
      if (islower(s[0])) return { IDENTIFIER, (idmp.contains(s) ? idmp[s] : idmp[s] = ++idc) };
      if (s[0] == '}') return LOOP_END;
      if (isdigit(s[0])) return { NUMBER, stoul(s) };
      if (s[0] == 'R') return RETURN;
      return BAD_TOKEN;
   } else return EOL;
}

Mat parseExpr(u32 id) {
   Mat res; res.setI();
   res[id][id] = 0;
   
   string exprStr; getline(cin, exprStr);
   stringstream exprStream(exprStr);

   for (;;) switch (auto curToken = nextToken(exprStream); curToken.type) {
   case IDENTIFIER:
      ++res[id][curToken.val];
      break;

   case NUMBER:
      res[id][0] += curToken.val;
      break;
   
   case EOL:
      return res;
   
   default: break;
   }
   assert(false);
   return res;
}

Mat parseLoop() {
   Mat res; res.setI();

   for (;;) switch(auto curToken = nextToken(cin); curToken.type) {
   case IDENTIFIER:
      res = parseExpr(curToken.val) * res;
      break;

   case LOOP_END: 
      return res;

   case NUMBER:   // A number at the beginning of a line -> Lexically a loop.
      res = (parseLoop() ^ curToken.val) * res;
      break;

   case RETURN:
      cout << res[nextToken(cin).val][0] << "\n";
      exit(0);

   default: break;
   }
}

int main() {
   ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
   parseLoop();
   return 0;
}
} // namespace SLV

int main() { return SLV::main(); }