AOJ2566 Restore Calculation
問題ページ
Restore Calculation | Aizu Online Judge
考えたこと
- 桁ごとに考えていけばよさそう
- 下の桁から繰り上がりがいるかとか考えればいける気持ちになる
- 場合分けが多すぎるので桁DPしたほうがよさそう
- dp[i][j] = (i桁目までで次の桁に繰り上がりがあるか) みたいなのをしたくなる
- 23通り場合分けを書けば通りそうなことはわかるが明らかに実装がつらそう
- ?をうまくまとめて遷移を書きたい
- まとめたいけど何も思いつかないのでしょうがないから8通り書くことにする
- leading-zeroが禁止されていることに気をつけつつ遷移を書いていくが8通りについてそれぞれ場合分けが8通りくらいあってつらすぎる
- 冷静になって考えると?の部分についてforを回して全探索しても計算量が余裕
- ?の部分について全探索して遷移させる
- n回WAを出しながらデバッグすると通った
桁DPに慣れてないのでそもそも遷移を考えるのに時間がかかった && ?の処理が下手で実装が地獄
もうちょっと実装を早くしたい
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; template<unsigned MOD> class ModInt { public: unsigned x; ModInt(): x(0) { } ModInt(signed y) : x(y >= 0 ? y % MOD : MOD - (-y) % MOD) {} unsigned get() const { return x; } // 逆数 ModInt inv() const { ll a = 1, p = x, e = MOD-2; while(e > 0) { if(e%2 == 0) {p = (p*p) % MOD; e /= 2;} else {a = (a*p) % MOD; e--;} } a %= MOD; return ModInt(a); } // e乗 ModInt pow(ll e) { ll a = 1, p = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % MOD; e /= 2;} else {a = (a*p) % MOD; e--;} } a %= MOD; return ModInt(a); } // 2のx乗 ModInt pow2() { ll a = 1, p = 2, e = x; while(e > 0) { if(e%2 == 0) {p = (p*p) % MOD; e /= 2;} else {a = (a*p) % MOD; e--;} } a %= MOD; return ModInt(a); } // Comparators bool operator <(ModInt b) { return x < b.x; } bool operator >(ModInt b) { return x > b.x; } bool operator<=(ModInt b) { return x <= b.x; } bool operator>=(ModInt b) { return x >= b.x; } bool operator!=(ModInt b) { return x != b.x; } bool operator==(ModInt b) { return x == b.x; } // increment, decrement ModInt operator++() { x++; return *this; } ModInt operator--() { x--; return *this; } // Basic Operations ModInt &operator+=(ModInt that) { x = ((ll)x+that.x)%MOD; return *this; } ModInt &operator-=(ModInt that) { x = ((((ll)x-that.x)%MOD)+MOD)%MOD; return *this; } ModInt &operator*=(ModInt that) { x = (ll)x * that.x % MOD; return *this; } // O(log(mod))かかるので注意 ModInt &operator/=(ModInt that) { x = (ll)x * that.inv() % MOD; return *this; } ModInt &operator%=(ModInt that) { x = (ll)x % that.x; return *this; } ModInt operator+(ModInt that)const{return ModInt(*this) += that;} ModInt operator-(ModInt that)const{return ModInt(*this) -= that;} ModInt operator*(ModInt that)const{return ModInt(*this) *= that;} ModInt operator/(ModInt that)const{return ModInt(*this) /= that;} ModInt operator%(ModInt that)const{return ModInt(*this) %= that;} }; typedef ModInt<1000000007> mint; // Input/Output ostream &operator<<(ostream& os, mint a) { return os << a.x; } istream &operator>>(istream& is, mint &a) { return is >> a.x; } mint dp[55][2]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); while(true) { string a, b, c; cin >> a; if(a=="0") break; cin >> b >> c; int n = a.size(); REP(i, 55) dp[i][0] = dp[i][1] = 0; dp[n][0] = 1; for(int i=n-1; i>=0; --i) { int A=a[i]-'0', B = b[i]-'0', C = c[i]-'0'; if(a[i]!='?'&&b[i]!='?'&&c[i]!='?') { if((A+B)%10==C) { if(A+B>=10) dp[i][1] += dp[i+1][0]; else dp[i][0] += dp[i+1][0]; } if((A+B+1)%10==C) { if(A+B+1>=10) dp[i][1] += dp[i+1][1]; else dp[i][0] += dp[i+1][1]; } } else if(a[i]=='?'&&b[i]!='?'&&c[i]!='?') { REP(j, 10) { if(i==0 && j==0) continue; if(i || (j+B)%10) { if((j+B)%10==C) { if(j+B>=10) dp[i][1] += dp[i+1][0]; else dp[i][0] += dp[i+1][0]; } } if(i || (j+B+1)%10) { if((j+B+1)%10==C) { if(j+B+1>=10) dp[i][1] += dp[i+1][1]; else dp[i][0] += dp[i+1][1]; } } } } else if(a[i]!='?'&&b[i]=='?'&&c[i]!='?') { REP(j, 10) { if(i==0 && j==0) continue; if(i || (j+A)%10) { if((j+A)%10==C) { if(j+A>=10) dp[i][1] += dp[i+1][0]; else dp[i][0] += dp[i+1][0]; } } if(i || (j+A+1)%10) { if((j+A+1)%10==C) { if(j+A+1>=10) dp[i][1] += dp[i+1][1]; else dp[i][0] += dp[i+1][1]; } } } } else if(a[i]!='?'&&b[i]!='?'&&c[i]=='?') { if(i || (A+B)%10) { if(A+B>=10) dp[i][1] += dp[i+1][0]; else dp[i][0] += dp[i+1][0]; } if(i || (A+B+1)%10) { if(A+B+1>=10) dp[i][1] += dp[i+1][1]; else dp[i][0] += dp[i+1][1]; } } else if(a[i]=='?'&&b[i]=='?'&&c[i]!='?') { REP(j, 10) REP(k, 10) { if(i==0 && (j==0 || k==0)) continue; if(i || (j+k)%10) { if((j+k)%10==C) { if(j+k>=10) dp[i][1] += dp[i+1][0]; else dp[i][0] += dp[i+1][0]; } } if(i || (j+k+1)%10) { if((j+k+1)%10==C) { if(j+k+1>=10) dp[i][1] += dp[i+1][1]; else dp[i][0] += dp[i+1][1]; } } } } else if(a[i]=='?'&&b[i]!='?'&&c[i]=='?') { REP(j, 10) { if(i==0 && j==0) continue; if(i || (j+B)%10) { if(j+B>=10) dp[i][1] += dp[i+1][0]; else dp[i][0] += dp[i+1][0]; } if(i || (j+B+1)%10) { if(j+B+1>=10) dp[i][1] += dp[i+1][1]; else dp[i][0] += dp[i+1][1]; } } } else if(a[i]!='?'&&b[i]=='?'&&c[i]=='?') { REP(j, 10) { if(i==0 && j==0) continue; if(i || (j+A)%10) { if(j+A>=10) dp[i][1] += dp[i+1][0]; else dp[i][0] += dp[i+1][0]; } if(i || (j+A+1)%10) { if(j+A+1>=10) dp[i][1] += dp[i+1][1]; else dp[i][0] += dp[i+1][1]; } } } else if(a[i]=='?'&&b[i]=='?'&&c[i]=='?') { REP(j, 10) REP(k, 10) { if(i==0 && (j==0 || k==0)) continue; if(i || (j+k)%10) { if(j+k>=10) dp[i][1] += dp[i+1][0]; else dp[i][0] += dp[i+1][0]; } if(i || (j+k+1)%10) { if(j+k+1>=10) dp[i][1] += dp[i+1][1]; else dp[i][0] += dp[i+1][1]; } } } } cout << dp[0][0] << endl; } return 0; }