結果

問題 No.189 SUPER HAPPY DAY
コンテスト
ユーザー codershifth
提出日時 2016-01-10 19:24:21
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 27 ms / 5,000 ms
コード長 2,116 bytes
コンパイル時間 2,241 ms
コンパイル使用メモリ 170,456 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-19 15:58:24
合計ジャッジ時間 2,927 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(int)(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

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;
        }
        cout<<(cnt-1+Mod)%Mod<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new SuperHappyDay();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0