前言: 一只小菜菜为了300分而疯狂的故事

梯度求解

思路: 
考虑到是逆波兰表达式, 所以栈是必需品
因为每个元素(或者表达式), 我们需要利用它 求导 和 没求导 的值
所以我们可以对于栈中的每个元素都记录下它的这两个属性值
对于 + 和 - 只需将它们求导值相+, 没求导值相-即可
那*咋办呢？突然想起高中念的经: 左导右不导~右导左不导

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 150, mod = 1e9 + 7;

int n, m;
string s;
int w[N], cnt;
int stack[N][2];
// 0表示未求导的值, 1表示求导以后的值

bool IsNum(char c)
{
    return '0' <= c && c <= '9';
}

int GetNum(int l, int r)
{
    int x = 0;
    while (l <= r)
        x = x * 10 + (s[l ++] - '0');
    return x;
}

void Push(int a, int b)
{
    stack[++ cnt][0] = a;
    stack[cnt][1] = b;
}

void solve(int x)
{
    for (int i = 0; i < s.size(); i ++)
    {
        if (s[i] == ' ') continue;

        if (s[i] == 'x')
        {
            i ++;
            int idx = i;
            while (IsNum(s[i])) i ++;
            idx = GetNum(idx, i - 1); // 把x后面的下标给读进来

            Push(w[idx], idx == x ? 1 : 0); // 如果这是被求偏导的未知数, 那求导以后就是1
        }
        else if (s[i] == '*')
        {
            int a = stack[cnt][0];
            int b = stack[cnt --][1];
            int c = stack[cnt][0];
            int d = stack[cnt --][1];
            // 不求偏导: 两个数都不求的积; 求偏导: 左导右不导 + 右导左不导
            Push((LL) a * c % mod, ((LL) a * d % mod + (LL) b * c % mod) % mod);
        }
        else if (s[i] == '+')
        {
            int a = stack[cnt][0];
            int b = stack[cnt --][1];
            int c = stack[cnt][0];
            int d = stack[cnt --][1];
            Push(((LL) a + c) % mod, ((LL) b + d) % mod);
        }
        else if (s[i] == '-') // 注意如果是'-', 可能是操作符, 也可能是常数前面的负号
        {
            if (s[i + 1] == ' ')
            {
                int a = stack[cnt][0];
                int b = stack[cnt --][1];
                int c = stack[cnt][0];
                int d = stack[cnt --][1];
                Push(((LL) c - a) % mod, ((LL) d - b) % mod);
            }
            else
            {
                i ++;
                int idx = i;
                while (IsNum(s[i])) i ++;
                idx = -1 * GetNum(idx, i - 1);
                Push(idx, 0);
            }
        }
        else if (IsNum(s[i]))
        {
            int idx = i;
            while (IsNum(s[i])) i ++;
            idx = GetNum(idx, i - 1);
            Push(idx, 0);
        }
    }
}

int main()
{
    scanf ("%d %d", &n, &m);
    getchar(); // 要把换行符读掉(坑死)
    getline(cin, s);
    s += ' ';

    while (m --)
    {
        int x;
        scanf ("%d", &x);

        for (int i = 1; i <= n; i ++) scanf ("%d", &w[i]);
        cnt = 0;
        solve(x);

        printf ("%lld\n", (stack[1][1] + mod) % mod);
    }
    return 0;
}