《等式填空》题目分析

本题是一道比较复杂的数位DP题目。

首先我们可以统计出，等号左边分别有几个问号处在个位、十位、百位、……；以及处在个位的有几个取值是0~9，有几个取值是1~9；处在十位的有几个取值是0~9，有几个取值是1~9……

我们不妨用q[i][0]表示处于第i位(i=0表示个位、i=1表示十位、以此类推……)并且取值可以是0~9的问号有几个；q[i][1]表示处于第i位并且取值可以是1~9的问号有几个。

考虑到S的长度|S|<=100，我们知道对于确定的i，q[i][0]+q[i][1] <= 50。

然后我们以样例??+?=23为例讲一下DP的思路：

我们按从个位到最高位依次处理。对于个位来说，是1个0~9的问号和1个1~9的问号，它们的和需要个位是3。

于是它们的和可能是3、13、23、33……；考虑到只有2个问号，于是可能的和只有3和13。

1)如果和是3，有3种可能：0+3, 1+2, 2+1 (注意第二个问号取值是1~9)。无论哪种选择，我们余下的问题都是从十位开始"?=2"这个问题。

2)如果和是13，有6种可能：4+9, 5+8, 6+7, 7+6, 8+5, 9+4。无论哪种选择，我们余下的问题都是从十位开始"?=1"这个问题。(由于13有进位)

所以我们通过处理最低位，将原问题变成了规模更小的子问题。"?=2"和"?=1"容易看出都只有一种填法，所以"??=23"的填法有3*1+6*1=9种。

回顾上面的过程，我们会反复遇到一个问题：X个0~9的问号和Y个1~9的问号，它们的和是Z，一共有几种填法。我们不妨用c[X][Y][Z]来表示这个问题的解。

在上面计算"??+?=23"时我们就用到了c[1][1][3]=3和c[1][1][13]=6。

考虑到S的长度|S|<=100，我们用到的c不会超过c[0..50][0..50][0.500]。求出c数组的值本身也是一个组合计数问题，可以用DP解决，这里不再赘述。

以下是用记忆化搜索求解的代码。

f[x][w]表示现在要填写所有(q[x][0]+q[x][1])第x位的问号(x=0代表个位、x=1代表十位……)，并且第0位~第x-1位总计带来的进位是w时，有几种不同的填法。
f[x][w]==-1表示f[x][w]还没求出来，需要用dp(x, w)求解。

m是等号右边的整数的位数。

d[0] d[1] d[2] ... d[m-1] 依次保存等号右边的整数的个位、十位、百位……数字。

curd是考虑到进位是w，所有处于x位的问号的和的个位数字。(其实就是 (d[x] - w) % 10，只不过要考虑不能是负数。)

long long dp(int x, int w) {
        if(x == m) {
                return w == 0;
        }
        if(f[x][w] != -1) {
                return f[x][w];
        }
        long long ret = 0;
        int curd = (d[x] + 10 - w % 10) % 10;
        for(int i = curd; i < 500; i+=10) {
                ret = (ret + c[q[x][0]][q[x][1]][i] * dp(x + 1, (i + w) / 10)) % MOD;
        }
        f[x][w] = ret;
        return ret;
}

最终的答案就是dp(0, 0)。