hiho一下第198周《等式填空》题目分析

10
1

《等式填空》题目分析

本题是一道比较复杂的数位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)。

3 answer(s)

0

我能问一句,哪里可以看到题目,而不是题目分析

0

你好,我想请问一下,为什么第x位的是与x+1位的相关联,而不是第x-1位的相关联呢,谢谢

2

dp大佬啊

write answer 切换为英文 切换为中文


转发分享