概要

以下のBNF表記の<expr>で表される数式Sと、S中の左からi番目の変数aの初期値 $a_i$ が与えられる。 $(b_q,x_q)$ からなるQ個のクエリに答えよ。

S中の左から $b_q$ 番目以外の変数は初期値のままで、 $b_q$ 番目の変数に $x_q$ を代入したときの数式の値を $10^9+7$ で割ったあまりを出力する。

<expr> ::= <term> | <expr> '+' <term> | <expr> '-' <term>
<term> ::= <value> | <term> '*' <value>
<value> ::= 'a' | '(' <expr> ')'

制約

$|S|\leq200000$
$Q\leq100000$

解法

構文解析ができれば、自動微分のノリでSの各ノードについての差分を再帰的に計算すればいい(Sはどのノードについてもそれの一次関数なので)。

abstract class Node
{
    public long Diff, Value;
    public abstract void GetDiff(long diff);
}
class VarNode : Node
{
    public int Id;
    public VarNode(int id, long val) { Id = id; Value = val; }
    public override void GetDiff(long diff) { Diff = diff; }
}
class OpNode : Node
{
    public char Op;
    public Node Left, Right;
    public OpNode(Node l, char o, Node r)
    {
        Left = l; Op = o; Right = r;
        switch (Op)
        {
            case '+': Value = (Left.Value + Right.Value) % K.MOD; break;
            case '*': Value = Left.Value * Right.Value % K.MOD; break;
         default: Value = (Left.Value - Right.Value + K.MOD) % K.MOD; break;
        }
    }
    public override void GetDiff(long diff)
    {
        Diff = diff;
        switch (Op)
        {
            case '+': Left.GetDiff(diff); Right.GetDiff(diff); break;
            case '*': Left.GetDiff(Right.Value * diff % K.MOD); Right.GetDiff(Left.Value * diff % K.MOD); break;
         default: Left.GetDiff(diff); Right.GetDiff((K.MOD - diff) % K.MOD); break;
        }
    }
}

なので、実質構文解析をする問題。まず、問題で与えられているBNFに沿って素直に再起下降してみる。

Node ParseE(ref int i)
{
    var n = ParseT(ref i);
    while (i < N && (S[i] == '+' || S[i] == '-'))
    {
        var op = S[i];
        i++;
        var m = ParseT(ref i);
        if (op == '+') n += m;
        else n -= m;
    }
    return n;
}
Node ParseT(ref int i)
{
    var n = ParseV(ref i);
    while (i < N && S[i] == '*')
    {
        var op = S[i];
        i++;
        n *= ParseV(ref i);
    }
    return n;
}
Node ParseV(ref int i)
{
    if (S[i] == '(')
    {
        i++;
        var n = ParseE(ref i);
        if (S[i] != ')') throw new Exception();
        i++;
        return n;
    }
    if (S[i] != 'a') throw new Exception();
    var x = new VarNode(Id, a[Id++]);
    leaves.Add(x);
    i++;
    return x;
}

再起下降の計算量はO(|S|)なので全体でO(|S|+Q)でAC…ではない。このままでは再起が深すぎてStackOverflowExceptionが出る。再起しない操車場アルゴリズムというのでやると、解ける。

ところで、StackOverflowExceptionを回避するにはどうしたらよいか。Stackでヒープ領域にスタックを確保すればいい(DFSで再起せずにStackを使うやつ)。

そのために、while文をifとgotoに書き直したあと、

関数の入り口
関数呼び出し後の復帰ポイント
gotoの行き先

にラベルを貼る。

int index = 0;
Node ParseE()
{
e0:
    var n = ParseT();
e1:
e2:
    if (index < N && (S[index] == '+' || S[index] == '-'))
    {
        var op = S[index];
        index++;
        var m = ParseT();
    e3:
        n = new OpNode(n, op, m);
        goto e2;
    }
    return n;
}
Node ParseT()
{
t0:
    var n = ParseV();
t1:
t2:
    if (index < N && S[index] == '*')
    {
        var op = S[index];
        index++;
        var m = ParseV();
    t3:
        n = new OpNode(n, op, m);
        goto t2;
    }
    return n;
}
Node ParseV()
{
v0:
    if (S[index] == '(')
    {
        index++;
        var n = ParseE();
    v1:
        index++;
        return n;
    }
    var x = new VarNode(Id, a[Id++]);
    leaves.Add(x);
    index++;
    return x;
}

次に、それぞれのラベルに対応するオブジェクト(ラベルの情報は型自体に持たせ、各ラベルにいるときに持つべき状態をメンバ変数にする)を作る。ラベルe1のように関数の戻り値を変数で受け取るラベルは、呼び出し先から帰ってきたときにはまだ変数に値がないので、メンバ変数に持たない。

struct E0 { }
struct E1 { }
struct E2 { public Node N; public E2(Node n) { N = n; } }
struct E3 { public Node N; public char Op; public E3(Node n, char op) { N = n; Op = op; } }
struct T0 { }
struct T1 { }
struct T2 { public Node N; public T2(Node n) { N = n; } }
struct T3 { public Node N; public char Op; public T3(Node n, char op) { N = n; Op = op; } }
struct V0 { }
struct V1 { }

あとは、さっきの再起関数をStackで書き直すだけ。再起するときは、復帰先と呼び出し先をスタックに積む。関数の返り値はobject ret;で管理。

Node Parse(string S, int[] a, List<Node> leaves)
{
    var index = 0;
    var id = 0;
    var N = S.Length;
    var st = new Stack<object>();
    object ret = null;
    st.Push(new E0());
    while (st.Count > 0)
    {
        var f = st.Pop();
        if (f is E0) { st.Push(new E1()); st.Push(new T0()); }
        else if (f is E1)
        {
            var n = (Node)ret;
            st.Push(new E2(n));
        }
        else if (f is E2)
        {
            var e2 = (E2)f;
            if (index < N && (S[index] == '+' || S[index] == '-'))
            {
                var op = S[index];
                index++;
                st.Push(new E3(e2.N, op));
                st.Push(new T0());
            }
            else ret = e2.N;
        }
        else if (f is E3)
        {
            var e3 = (E3)f;
            var m = (Node)ret;
            var n = new OpNode(e3.N, e3.Op, m);
            st.Push(new E2(n));
        }
        else if (f is T0) { st.Push(new T1()); st.Push(new V0()); }
        else if (f is T1)
        {
            var n = (Node)ret;
            st.Push(new T2(n));
        }
        else if (f is T2)
        {
            var t2 = (T2)f;
            if (index < N && S[index] == '*')
            {
                var op = S[index];
                index++;
                st.Push(new T3(t2.N, op));
                st.Push(new V0());
            }
            else ret = t2.N;
        }
        else if (f is T3)
        {
            var t3 = (T3)f;
            var m = (Node)ret;
            var n = new OpNode(t3.N, t3.Op, m);
            st.Push(new T2(n));
        }
        else if (f is V0)
        {
            if (S[index] == '(')
            {
                index++;
                st.Push(new V1());
                st.Push(new E0());
            }
            else
            {
                var x = new VarNode(id, a[id++]);
                leaves.Add(x);
                index++;
                ret = x;
            }
        }
        else if (f is V1) index++;
    }
    return (Node)ret;
}