結果

問題 No.189 SUPER HAPPY DAY
ユーザー ttkkggwwttkkggww
提出日時 2022-09-10 18:31:45
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 34 ms / 5,000 ms
コード長 1,737 bytes
コンパイル時間 5,012 ms
コンパイル使用メモリ 264,456 KB
実行使用メモリ 16,256 KB
最終ジャッジ日時 2024-11-26 23:35:24
合計ジャッジ時間 5,829 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
16,128 KB
testcase_01 AC 6 ms
16,000 KB
testcase_02 AC 7 ms
16,128 KB
testcase_03 AC 7 ms
16,128 KB
testcase_04 AC 8 ms
16,128 KB
testcase_05 AC 7 ms
16,000 KB
testcase_06 AC 7 ms
16,128 KB
testcase_07 AC 6 ms
16,000 KB
testcase_08 AC 7 ms
16,256 KB
testcase_09 AC 7 ms
16,128 KB
testcase_10 AC 7 ms
15,872 KB
testcase_11 AC 6 ms
16,020 KB
testcase_12 AC 7 ms
16,128 KB
testcase_13 AC 24 ms
16,000 KB
testcase_14 AC 32 ms
16,128 KB
testcase_15 AC 26 ms
16,128 KB
testcase_16 AC 26 ms
16,016 KB
testcase_17 AC 27 ms
16,000 KB
testcase_18 AC 25 ms
16,000 KB
testcase_19 AC 34 ms
16,024 KB
testcase_20 AC 15 ms
16,128 KB
testcase_21 AC 19 ms
16,128 KB
testcase_22 AC 10 ms
16,128 KB
testcase_23 AC 22 ms
16,128 KB
testcase_24 AC 17 ms
16,128 KB
testcase_25 AC 31 ms
16,128 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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();
}
0