結果

問題 No.189 SUPER HAPPY DAY
ユーザー ttkkggww
提出日時 2022-09-10 18:31:45
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 49 ms / 5,000 ms
コード長 1,737 bytes
コンパイル時間 4,971 ms
コンパイル使用メモリ 254,472 KB
最終ジャッジ日時 2025-02-07 04:07:20
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /usr/include/atcoder/modint:1,
                 from /usr/include/atcoder/convolution.hpp:11,
                 from /usr/include/atcoder/convolution:1,
                 from /usr/include/atcoder/all:1,
                 from main.cpp:3:
In member function ‘atcoder::dynamic_modint<id>::mint& atcoder::dynamic_modint<id>::operator+=(const mint&) [with int id = -1]’,
    inlined from ‘void solve()’ at main.cpp:57:67:
/usr/include/atcoder/modint.hpp:192:9: warning: iteration 1 invokes undefined behavior [-Waggressive-loop-optimizations]
  192 |         _v += rhs._v;
      |         ^~
main.cpp: In function ‘void solve()’:
main.cpp:55:32: note: within this loop
   55 |                 for(int j = 1;j<10;j++){
      |                               ~^~~

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/all>
using namespace atcoder;
using ll = long long;
string M,D;
using mint = modint;
mint dp1[202][2][4000];
mint dp2[202][2][4000];
void solve(){
    for(auto &i:M)i-='0';
    for(auto &i:D)i-='0';
    for(int i = 1;i<M[0];i++){
        dp1[1][1][i+2000-1] = 1;
    }
    dp1[1][0][M[0]+2000-1] = 1;
    for(int i =1;i<M.size();i++){
        for(int j = 1;j<10;j++){
            dp1[i+1][1][j+2000-1] += 1;
        }
        for(int j = 0;j<10;j++){
            for(int k =0;k<4000;k++){
                if(k+j<4000){
                    dp1[i+1][1][k+j] += dp1[i][1][k];
                }
                
            }
        }
        for(int j = 0;j<M[i];j++){
            for(int k = 0;k<4000;k++){
                if(k+j<4000){
                    dp1[i+1][1][k+j] += dp1[i][0][k];
                }
            }
        }
        for(int k = 0;k<4000;k++){
            if(k+M[i]<4000){
                dp1[i+1][0][k+M[i]] += dp1[i][0][k];
            }
        }
    }
    for(int i = 0;i<4000;i++){
        for(int j = 1;j<D[0];j++){
            if(i-j+1>=0)
                dp2[1][1][i-j+1] += dp1[M.size()][0][i] + dp1[M.size()][1][i];
        }
    }
    for(int i = 0;i<4000;i++){
        if(i-D[0]+1>=0){
            dp2[1][0][i-D[0]+1] += dp1[M.size()][0][i] + dp1[M.size()][1][i];
        }
    }
    for(int i = 1;i<D.size();i++){
        for(int j = 1;j<10;j++){
            for(int k =0;k< 4000;k++){
                dp2[i+1][1][k-j+1] += dp1[M.size()][0][k] + dp1[M.size()][1][k];
            }
        }
        for(int k = 0;k<4000;k++){
            for(int j = 0;j<10;j++){
                if(k-j>=0){
                    dp2[i+1][1][k-j] += dp2[i][1][k];
                }
            }
            for(int j = 0;j<D[i];j++){
                if(k-j>=0){
                    dp2[i+1][1][k-j] += dp2[i][0][k];
                }
            }
            if(k-D[i]>=0){
                dp2[i+1][0][k-D[i]] += dp2[i][0][k];
            }
        }
    }
    mint ans = dp2[D.size()][0][2000] + dp2[D.size()][1][2000];
    cout<<ans.val()<<endl;
}
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    mint::set_mod(1000000009);
    cin >> M >> D;
    solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0