結果
問題 |
No.1417 100の倍数かつ正整数(2)
|
ユーザー |
|
提出日時 | 2021-03-21 18:14:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 81 ms / 3,000 ms |
コード長 | 1,594 bytes |
コンパイル時間 | 1,418 ms |
コンパイル使用メモリ | 119,928 KB |
最終ジャッジ日時 | 2025-01-19 20:54:52 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
#include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <map> #include <set> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cstdio> #include <limits> #include <vector> #include <cstdlib> #include <numeric> #include <sstream> #include <iostream> #include <algorithm> #include <functional> #include <iomanip> #include <unordered_map> #include <memory.h> #include <unordered_set> #include <fstream> using namespace std; const long long int MOD = 1e9 + 7; //dp long long int dp[10005][2][100]; int main(void) { cin.tie(0); ios::sync_with_stdio(false); string s; int n; cin >> s; int x = s[0] - '0'; for (int i = 1; i < x; i++) { dp[1][0][i] += 1; } dp[1][1][x] += 1; n = s.length(); for (int i = 1; i < n; i++) { for (int j = 1; j < 10; j++) { dp[i + 1][0][j] += 1; dp[i + 1][0][j] %= MOD; } int x = s[i] - '0'; for (int j = 0; j < 100; j++) { for (int k = 1; k <= 9; k++) { dp[i + 1][0][(j * k) % 100] += dp[i][0][j]; dp[i + 1][0][(j * k) % 100] %= MOD; } for (int k = 1; k < x; k++) { dp[i + 1][0][(j * k) % 100] += dp[i][1][j]; dp[i + 1][0][(j * k) % 100] %= MOD; } if (x != 0) { dp[i + 1][1][(j * x) % 100] += dp[i][1][j]; dp[i + 1][1][(j * x) % 100] %= MOD; } } } //cout << dp[n][0][0] << ' ' << dp[n][1][0] << '\n'; long long int res = dp[n][0][0] + dp[n][1][0]; res %= MOD; cout << res << '\n'; return 0; }