CSU 1374 Restore Calculation 数位DP

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 typedef long long ll;
 8 
 9 const ll MOD = (ll)1e9+7;
10 const int MAXN = 100;
11 
12 ll dp[MAXN][2];
13 char str[3][MAXN];
14 
15 int main() {
16     #ifdef Phantom01
17         freopen("CSU1374.txt", "r", stdin);
18     #endif // Phantom01
19 
20     while (scanf("%s", str[0])!=EOF) {
21         if (‘0‘==str[0][0]&&‘\0‘==str[0][1]) return 0;
22         scanf("%s%s", str[1], str[2]);
23         memset(dp, 0, sizeof(dp));
24         int len = strlen(str[0]);
25         dp[len][0] = 1;
26         for (int l = len-1; l > 0; l--) //第l位
27             for (int p = 0; p < 2; p++) if (dp[l+1][p]>0) //进位
28                 for (int i = 0; i < 10; i++) if (‘?‘==str[0][l] || i==(str[0][l]-‘0‘))  //a[l]
29                     for (int j = 0; j < 10; j++) if (‘?‘==str[1][l] || j==(str[1][l]-‘0‘))  //b[l]
30                         if (‘?‘==str[2][l] || (i+j+p)%10==(str[2][l]-‘0‘)) {
31                             ll &now = dp[l][(i+j+p)/10];
32                             now = (now+dp[l+1][p])%MOD;
33                         }
34         //最后一位不为0
35         for (int p = 0; p < 2; p++) if (dp[1][p]>0) //进位
36             for (int i = 1; i < 10; i++) if (‘?‘==str[0][0] || i==(str[0][0]-‘0‘))  //a[l]
37                 for (int j = 1; j < 10; j++) if (‘?‘==str[1][0] || j==(str[1][0]-‘0‘))  //b[l]
38                     if (‘?‘==str[2][0] || (i+j+p)%10==(str[2][0]-‘0‘)) {
39                         ll &now = dp[0][(i+j+p)/10];
40                         now = (now+dp[1][p])%MOD;
41                     }
42 
43         printf("%lld\n", dp[0][0]);
44     }
45 }