No.189 SUPER HAPPY DAY

No.189 SUPER HAPPY DAY - yukicoder

• TDPC E-数 でやった桁 DP を使う。桁を大きいほうから DP するのがポイント
• 最後は 00...0 と全て 0 のケースを除くことことが必要。

const ll Mod = 1000000009;
class SuperHappyDay
{
public:
    void solve(void)
    {
        string MD[2];
        cin>>MD[0]>>MD[1];

        // 数字和の最大値は 200*9 = 1800 程度
        // M,D それぞれで数字和をカウントしておいて、和が一致するものの数をかければ良い

        // 大きい方の桁から下ってやることで DP 場合分けを減らす
        vector<vector<ll>> dpMD[2];
        REP(l,2)
        {
            auto &dp = dpMD[l];
            dp = vector<vector<ll>>(2,vector<ll>(2001,0));

            const auto &S = MD[l];
            dp[1][S[0]-'0'] = 1;
            REP(x,S[0]-'0') dp[0][x] = 1;

            FOR(i,1,S.size())
            {
                vector<vector<ll>> tmp(2,vector<ll>(2001,0));
                REP(x,10)
                for (int j = 0; x+j <= 2000; ++j)
                {
                    if (x < S[i]-'0')
                    {
                        REP(k,2)
                            (tmp[0][x+j] += dp[k][j]) %= Mod;
                    }
                    else if (S[i]-'0' == x)
                    {
                        REP(k,2)
                            (tmp[k][x+j] += dp[k][j]) %= Mod;
                    }
                    else
                    {
                        (tmp[0][x+j] += dp[0][j]) %= Mod;
                    }
                }
                dp = tmp;
            }
        }
        ll cnt = 0;
        REP(k,2)
        REP(j,2)
        REP(i,2001)
        {
            // i が一致するもの同士の組み合わせを数える
            (cnt += dpMD[0][j][i]*dpMD[1][k][i]%Mod) %= Mod;
        }
        // 0000...0 のケースを取り除く
        cout<<(cnt-1+Mod)%Mod<<endl;
    }
};