AOJ2566 Restore Calculation
問題
3つのN桁の数A, B, Cがある。いくつかの数字は'?'となっている。
'?'には、数字の先頭であれば'1'から'9'が入り、先頭でなければ'0'から'9'が入る。
A + B = C が成立するパターン数を求めよ。(MOD 10^9+7)
解説
各々の数を逆順にして左から見ていき、桁の上がりを0, 1, 2の何れかを持ってDPする。
dp[桁][桁上りの数] := パターン数
桁上りの値carryは、next_carry = (a + b + carry) / 10
桁の値numは、num = (a + b + carry) % 10
として計算できる。
固定された数字と'?'の数字との場合分けの方法には色々あると思うが、自分は先に各数字の各桁に対して'?'か数字か調べておいて、vectorに10個または固定の1個を詰めておいた。そうすることで、選ぶ数字についてはvectorの中身を見ることでDPの中で場合分けを考慮しないようにした。
string a, b, c; ll dp[51][3]; int main() { while(cin >> a) { if(a == "0") break; cin >> b >> c; reverse(all(a)); reverse(all(b)); reverse(all(c)); int n = a.size(); vector<vector<int>> va(n), vb(n), vc(n); rep(i, n) { if(a[i] == '?') REP(k, i==n-1, 10) va[i].push_back(k); else va[i].push_back(a[i]-'0'); if(b[i] == '?') REP(k, i==n-1, 10) vb[i].push_back(k); else vb[i].push_back(b[i]-'0'); if(c[i] == '?') REP(k, i==n-1, 10) vc[i].push_back(k); else vc[i].push_back(c[i]-'0'); } zero(dp); dp[0][0] = 1; rep(i, n) rep(carry, 3) { for(auto& da: va[i]) for(auto& db: vb[i]) for(auto& dc: vc[i]) { int num = (da + db + carry) % 10; int ncr = (da + db + carry) / 10; if(num == dc) { dp[i+1][ncr] += dp[i][carry]; dp[i+1][ncr] %= MOD; } } } cout << dp[n][0] << endl; } return 0; }