結果
問題 | No.260 世界のなんとか3 |
ユーザー | yukirin |
提出日時 | 2017-04-13 19:47:12 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 86 ms / 2,000 ms |
コード長 | 3,051 bytes |
コンパイル時間 | 1,099 ms |
コンパイル使用メモリ | 106,728 KB |
実行使用メモリ | 18,504 KB |
最終ジャッジ日時 | 2023-09-25 16:28:03 |
合計ジャッジ時間 | 3,137 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,400 KB |
testcase_01 | AC | 2 ms
5,428 KB |
testcase_02 | AC | 2 ms
5,524 KB |
testcase_03 | AC | 68 ms
18,456 KB |
testcase_04 | AC | 69 ms
18,436 KB |
testcase_05 | AC | 15 ms
9,536 KB |
testcase_06 | AC | 11 ms
7,356 KB |
testcase_07 | AC | 48 ms
15,784 KB |
testcase_08 | AC | 34 ms
11,756 KB |
testcase_09 | AC | 20 ms
9,552 KB |
testcase_10 | AC | 54 ms
17,680 KB |
testcase_11 | AC | 50 ms
15,708 KB |
testcase_12 | AC | 32 ms
13,652 KB |
testcase_13 | AC | 11 ms
8,460 KB |
testcase_14 | AC | 46 ms
15,716 KB |
testcase_15 | AC | 14 ms
9,020 KB |
testcase_16 | AC | 41 ms
15,632 KB |
testcase_17 | AC | 33 ms
13,660 KB |
testcase_18 | AC | 31 ms
13,788 KB |
testcase_19 | AC | 40 ms
13,732 KB |
testcase_20 | AC | 29 ms
11,748 KB |
testcase_21 | AC | 27 ms
13,788 KB |
testcase_22 | AC | 46 ms
15,636 KB |
testcase_23 | AC | 6 ms
5,928 KB |
testcase_24 | AC | 36 ms
13,664 KB |
testcase_25 | AC | 44 ms
11,600 KB |
testcase_26 | AC | 27 ms
11,564 KB |
testcase_27 | AC | 2 ms
5,504 KB |
testcase_28 | AC | 51 ms
18,404 KB |
testcase_29 | AC | 86 ms
18,504 KB |
ソースコード
#include <algorithm> #include <bitset> #include <cfloat> #include <cmath> #include <ctime> #include <deque> #include <iomanip> #include <iostream> #include <limits> #include <list> #include <map> #include <numeric> #include <queue> #include <random> #include <set> #include <sstream> #include <stack> #include <string> #include <typeindex> #include <typeinfo> #include <vector> #define DEBUG(x) cout << #x << ": " << x << endl #define INFILE() freopen("input.txt", "r", stdin) #define REP(i, a, b) for (int i = a; i < b; i++) #define ALL(s) begin(s), end(s) #define RALL(s) rbegin(s), rend(s) using namespace std; using ll = long long; using ull = unsigned long long; using i_i = pair<int, int>; using ll_i = pair<ll, int>; using i_ll = pair<int, ll>; using d_i = pair<double, int>; using ll_ll = pair<ll, ll>; using d_d = pair<double, double>; static constexpr ll LL_MOD = 1000000007; static constexpr int I_MOD = 1000000007; static constexpr double EPS = numeric_limits<double>::epsilon(); static constexpr double PI = 3.14159265358979323846264338327950288; template <class T> static void scan(vector<T> &v); static void scan(vector<string> &v, bool isWord = true); ll dp[10010][2][2][3][8]; ll dp2[10010][2][2][3][8]; int main(int argc, char *argv[]) { // INFILE(); string a, b; cin >> a >> b; int la = a.size(), lb = b.size(); dp[0][0][0][0][0] = dp2[0][0][0][0][0] = 1; REP(i, 0, la) REP(less, 0, 2) REP(t, 0, 2) REP(m3, 0, 3) REP(m8, 0, 8) { int lim = less ? 9 : a[i] - '0'; REP(n, 0, lim + 1) { dp[i + 1][less || n < lim][t || n == 3][(m3 + n) % 3] [(m8 * 10 + n) % 8] += (dp[i][less][t][m3][m8] % LL_MOD); } } REP(i, 0, lb) REP(less, 0, 2) REP(t, 0, 2) REP(m3, 0, 3) REP(m8, 0, 8) { int lim = less ? 9 : b[i] - '0'; REP(n, 0, lim + 1) { dp2[i + 1][less || n < lim][t || n == 3][(m3 + n) % 3] [(m8 * 10 + n) % 8] += (dp2[i][less][t][m3][m8] % LL_MOD); } } ll countA = 0, countB = 0; REP(t, 0, 2) REP(m3, 0, 3) REP(m8, 0, 8) { if ((t || (m3 == 0)) && (m8 != 0)) { (countA += dp[la][1][t][m3][m8]) %= LL_MOD; } } REP(less, 0, 2) REP(t, 0, 2) REP(m3, 0, 3) REP(m8, 0, 8) { if ((t || (m3 == 0)) && (m8 != 0)) { (countB += dp2[lb][less][t][m3][m8]) %= LL_MOD; } } cout << (countB - countA + LL_MOD) % LL_MOD << "\n"; return 0; } template <class T> static void scan(vector<T> &v) { map<type_index, const char *const> m = {{typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}}; auto tFormat = m[typeid(T)]; for (T &n : v) { scanf(tFormat, &n); } } static void scan(vector<string> &v, bool isWord) { if (isWord) { for (auto &n : v) { cin >> n; } return; } int i = 0, size = v.size(); string s; getline(cin, s); if (s.size() != 0) { i++; v[0] = s; } for (; i < size; ++i) { getline(cin, v[i]); } }