読者です 読者をやめる 読者になる 読者になる

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;
}