题目链接：点击打开链接
思路：用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
",kase,ans);
}
return 0;
}