結果
問題 | No.260 世界のなんとか3 |
ユーザー | rsk0315 |
提出日時 | 2017-01-21 19:31:10 |
言語 | C++14 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 481 ms / 2,000 ms |
コード長 | 3,364 bytes |
コンパイル時間 | 1,580 ms |
コンパイル使用メモリ | 72,436 KB |
実行使用メモリ | 10,624 KB |
最終ジャッジ日時 | 2023-08-24 19:21:52 |
合計ジャッジ時間 | 7,560 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 2 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 379 ms
10,612 KB |
testcase_04 | AC | 381 ms
10,624 KB |
testcase_05 | AC | 73 ms
5,272 KB |
testcase_06 | AC | 49 ms
4,496 KB |
testcase_07 | AC | 258 ms
9,096 KB |
testcase_08 | AC | 179 ms
9,156 KB |
testcase_09 | AC | 100 ms
5,840 KB |
testcase_10 | AC | 292 ms
8,780 KB |
testcase_11 | AC | 273 ms
9,412 KB |
testcase_12 | AC | 165 ms
7,844 KB |
testcase_13 | AC | 47 ms
4,380 KB |
testcase_14 | AC | 246 ms
9,044 KB |
testcase_15 | AC | 66 ms
4,380 KB |
testcase_16 | AC | 218 ms
7,900 KB |
testcase_17 | AC | 170 ms
6,584 KB |
testcase_18 | AC | 165 ms
6,084 KB |
testcase_19 | AC | 214 ms
9,152 KB |
testcase_20 | AC | 152 ms
6,572 KB |
testcase_21 | AC | 133 ms
7,044 KB |
testcase_22 | AC | 248 ms
8,028 KB |
testcase_23 | AC | 24 ms
4,376 KB |
testcase_24 | AC | 190 ms
8,560 KB |
testcase_25 | AC | 243 ms
10,128 KB |
testcase_26 | AC | 139 ms
10,156 KB |
testcase_27 | AC | 1 ms
4,380 KB |
testcase_28 | AC | 277 ms
10,600 KB |
testcase_29 | AC | 481 ms
10,596 KB |
ソースコード
#include <cstdio> #include <vector> #include <functional> #include <cstdint> #include <string> #include <utility> using namespace std; struct DigitDP { using Func=function<size_t (size_t, size_t)>; vector<Func> funcs; vector<size_t> ubs; size_t size, n; int64_t mod; vector<int64_t> dp; DigitDP(int64_t mod): size(2), mod(mod) {} void add_func(size_t ub, const Func &&func) { size *= ub; ubs.push_back(ub); funcs.push_back(func); } void store(const string &number) { n = number.length(); dp.assign(size*(n+1), 0); dp[0]=1; vector<size_t> indices(funcs.size()); for (size_t pos=0; pos<n; ++pos) for (size_t less=0; less<2; ++less) dfs(number, pos, less, dp, indices); } template <class... Index> pair<int64_t, int64_t> get(Index... k) { size_t li=(n<<1), ei=(n<<1|1); li = get_index(0, li, k...); ei = get_index(0, ei, k...); pair<int64_t, int64_t> res(dp[ei], dp[li]); (res.second += res.first) %= mod; return res; } template <class First, class... Rest> size_t get_index(size_t i, size_t index, First first, Rest... rest) { return get_index(i+1, index*ubs[i]+first, rest...); } size_t get_index(size_t i, size_t index) { return index; } void dfs( const string &number, size_t pos, size_t less, vector<int64_t> &dp, vector<size_t> &indices, size_t index=0 ) { if (index == funcs.size()) { // update dp table size_t ub=less? 9:(number[pos]-'0'); for (size_t d=0; d<=ub; ++d) { size_t next=pos+1, prev=pos; (next <<= 1) |= (less || d < ub); (prev <<= 1) |= less; for (size_t i=0; i<indices.size(); ++i) { (next *= ubs[i]) += funcs[i](indices[i], d); (prev *= ubs[i]) += indices[i]; } (dp[next] += dp[prev]) %= mod; } return; } for (indices[index]=0; indices[index]<ubs[index]; ++indices[index]) dfs(number, pos, less, dp, indices, index+1); } }; pair<int64_t, int64_t> count(const string &number, int64_t mod=1e9+7) { DigitDP d(mod); d.add_func(2, [](size_t k, size_t d)->size_t { return k || d == 3; }); d.add_func(3, [](size_t l, size_t d)->size_t { return (l + d) % 3; }); d.add_func(8, [](size_t m, size_t d)->size_t { return (m * 10 + d) % 8; }); d.store(number); pair<int64_t, int64_t> res; for (size_t k=0; k<2; ++k) for (size_t l=0; l<3; ++l) for (size_t m=0; m<8; ++m) if ((k || l == 0) && m != 0) { pair<int64_t, int64_t> tmp=d.get(k, l, m); (res.first += tmp.first) %= mod; (res.second += tmp.second) %= mod; } return res; } int64_t count(const string &l, const string &r, int64_t mod=1e9+7) { int64_t ub=count(r).second, lb=count(l).first; return (ub-lb+mod) % mod; } int main() { string A, B; { char tmp[16384]; scanf("%s", tmp); A = tmp; scanf("%s", tmp); B = tmp; } printf("%lld\n", count(A, B)); return 0; }