题目链接：点击打开链接

思路：用d[i][a][b][c][is]表示当前到了第i位， 三个数的i位各自是a,b,c， 是否有进位 ， 的方法数。

细节參见代码：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<string>

#include<vector>

#include<stack>

#include<bitset>

#include<cstdlib>

#include<cmath>

#include<set>

#include<list>

#include<deque>

#include<map>

#include<queue>

#define Max(a,b) ((a)>(b)?(a):(b))

#define Min(a,b) ((a)<(b)?(a):(b))

using namespace std;

typedef long long ll;

typedef long double ld;

const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;

const int mod = 1000000000 + 7;

const int INF = 0x3f3f3f3f;

// & 0x7FFFFFFF

const int seed = 131;

const ll INF64 = ll(1e18);

const int maxn = 15;

int T,n,m,len,vis[maxn][maxn][maxn][maxn][2],len1,len2,len3,kase = 0;

char a[maxn],b[maxn],c[maxn],s[100];

ll d[maxn][maxn][maxn][maxn][2];

ll dp(int pos, int bb, int cc, int dd, int is) {

    ll& ans = d[pos][bb][cc][dd][is];

    if(pos > len) return is == 0;

    if(vis[pos][bb][cc][dd][is] == kase) return ans;

    vis[pos][bb][cc][dd][is] = kase;

    ans = 0;

        if(a[pos] == '?' && b[pos] == '?') {

            for(int i = 0; i < 10; i++) {

                for(int j = 0; j < 10; j++) {

                    if(pos == len1 && i == 0 && len1 != 1) continue;

                    if(pos == len2 && j == 0&& len2 != 1) continue;

                    int cur = i + j + is;

                    int res = 0;

                    if(cur >= 10) {

                        cur -= 10; ++res;

                    }

                    if(c[pos] == '?

' && !(pos == len3 && cur == 0 && len3 != 1)) ans += dp(pos+1,i, j,cur, res);

                    else if(c[pos]-'0' == cur) ans += dp(pos+1, i,j,cur, res);

                }

            }

        }

        else if(a[pos] == '?') {

            for(int i = 0; i < 10; i++) {

                if(pos == len1 && i == 0&& len1 != 1) continue;

                int cur = i + b[pos]-'0' + is;

                int res = 0;

                if(cur >= 10) {

                    cur -= 10; ++res;

                }

                if(c[pos] == '?

' && !(pos == len3 && cur == 0 && len3 != 1)) ans += dp(pos+1,i,b[pos]-'0',cur, res);

                else if(c[pos]-'0' == cur) ans += dp(pos+1,i,b[pos]-'0',cur, res);

            }

        }

        else if(b[pos] == '?') {

            for(int i = 0; i < 10; i++) {

                if(pos == len2 && i == 0&& len2 != 1) continue;

                int cur = i + a[pos]-'0' + is;

                int res = 0;

                if(cur >= 10) {

                    cur -= 10; ++res;

                }

                if(c[pos] == '?' && !(pos == len3 && cur == 0 && len3 != 1)) ans += dp(pos+1,a[pos]-'0',i,cur, res);

                else if(c[pos]-'0' == cur) ans += dp(pos+1,a[pos]-'0',i,cur, res);

            }

        }

        else {

            int cur = a[pos]-'0' + b[pos]-'0' + is;

            int res = 0;

            if(cur >= 10) {

                cur -= 10; ++res;

            }

            if(c[pos] == '?' && !(pos == len3 && cur == 0 && len3 != 1)) ans += dp(pos+1, a[pos]-'0',b[pos]-'0',cur, res);

            else if(c[pos]-'0' == cur) ans += dp(pos+1, a[pos]-'0',b[pos]-'0',cur, res);

        }

    return ans;

}

int main() {

    while(~scanf("%s",s+1)) {

        len = strlen(s+1);

        len1 = 0; len2 = 0; len3 = 0;

        int id = 0;

        for(int i = len; i >= 1; i--) {

            if(s[i] == '=' || s[i] == '+') { id++; continue; }

            if(id == 0) {

                c[++len3] = s[i];

            }

            else if(id == 1) {

                b[++len2] = s[i];

            }

            else {

                a[++len1] = s[i];

            }

        }

        len = max(len1, max(len2, len3));//补全不足的。 降低代码量

        for(int i = len1+1; i <= len; i++) a[i] = '0';

        for(int i = len2+1; i <= len; i++) b[i] = '0';

        for(int i = len3+1; i <= len; i++) c[i] = '0';

        ++kase;

        ll ans = dp(1, 0 , 0, 0, 0);

        printf("Case %d: %I64d\n",kase,ans);

    }

    return 0;

}