結果
問題 | No.1417 100の倍数かつ正整数(2) |
ユーザー |
![]() |
提出日時 | 2021-03-24 02:24:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,008 ms / 3,000 ms |
コード長 | 1,926 bytes |
コンパイル時間 | 4,223 ms |
コンパイル使用メモリ | 230,688 KB |
実行使用メモリ | 24,320 KB |
最終ジャッジ日時 | 2024-11-26 10:19:36 |
合計ジャッジ時間 | 11,500 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)#define rep(i,n) REP(i,0,n)#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)#define ALLOF(c) (c).begin(), (c).end()typedef long long ll;typedef unsigned long long ull;using mint = modint1000000007;//using mint = modint998244353;bool visited[10005][2][100][2];mint dp[10005][2][100][2];string S;mint solve(int i, int lz, int m, int smaller){if(visited[i][lz][m][smaller]) return dp[i][lz][m][smaller];mint ret(0);int x = 0;if(i<S.size()) x = S[i]-'0';if(i == 0){if(smaller == 0){if(1 <= m && m <= x) return mint(1);}else{if(1 <= m && m <= 9) return mint(1);}return mint(0);}if(smaller == 0){if(lz == 1){if(x != 0){rep(j,100){if((j*x)%100 == m) ret += solve(i-1,0,j,0);}REP(y,1,x){rep(j,100){if((j*y)%100 == m) ret += solve(i-1,0,j,1);}}ret += solve(i-1,1,m,1);}else{ret += solve(i-1,1,m,0);}}else{if(x != 0){rep(j,100){if((j*x)%100 == m) ret += solve(i-1,0,j,0);}REP(y,1,x){rep(j,100){if((j*y)%100 == m) ret += solve(i-1,0,j,1);}}}}}else{if(lz == 1){REP(y,1,10){rep(j,100){if((j*y)%100 == m) ret += solve(i-1,0,j,1);}}ret += solve(i-1,1,m,1);}else{REP(y,1,10){rep(j,100){if((j*y)%100 == m) ret += solve(i-1,0,j,1);}}}}visited[i][lz][m][smaller] = true;return dp[i][lz][m][smaller] = ret;}int main(){cin >> S;int N = S.size();reverse(ALLOF(S));cout << solve(N, 1, 0, 0).val() << endl;return 0;}