結果
問題 | No.260 世界のなんとか3 |
ユーザー | rsk0315 |
提出日時 | 2017-01-21 20:49:28 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 501 ms / 2,000 ms |
コード長 | 3,462 bytes |
コンパイル時間 | 1,279 ms |
コンパイル使用メモリ | 74,148 KB |
実行使用メモリ | 10,200 KB |
最終ジャッジ日時 | 2023-08-24 19:22:54 |
合計ジャッジ時間 | 7,256 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge15 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 394 ms
10,180 KB |
testcase_04 | AC | 395 ms
10,140 KB |
testcase_05 | AC | 75 ms
5,552 KB |
testcase_06 | AC | 51 ms
4,528 KB |
testcase_07 | AC | 267 ms
9,084 KB |
testcase_08 | AC | 185 ms
9,152 KB |
testcase_09 | AC | 104 ms
5,852 KB |
testcase_10 | AC | 302 ms
8,356 KB |
testcase_11 | AC | 282 ms
9,428 KB |
testcase_12 | AC | 170 ms
7,784 KB |
testcase_13 | AC | 49 ms
4,380 KB |
testcase_14 | AC | 255 ms
9,156 KB |
testcase_15 | AC | 68 ms
4,380 KB |
testcase_16 | AC | 223 ms
7,776 KB |
testcase_17 | AC | 176 ms
6,524 KB |
testcase_18 | AC | 169 ms
6,048 KB |
testcase_19 | AC | 222 ms
9,080 KB |
testcase_20 | AC | 157 ms
6,576 KB |
testcase_21 | AC | 138 ms
7,008 KB |
testcase_22 | AC | 255 ms
8,100 KB |
testcase_23 | AC | 25 ms
4,376 KB |
testcase_24 | AC | 197 ms
8,624 KB |
testcase_25 | AC | 254 ms
10,200 KB |
testcase_26 | AC | 144 ms
10,084 KB |
testcase_27 | AC | 2 ms
4,380 KB |
testcase_28 | AC | 287 ms
10,088 KB |
testcase_29 | AC | 501 ms
10,104 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 tight=0; tight<2; ++tight) modify_table(number, pos, tight, dp, indices); } void modify_table( const string &number, size_t pos, size_t tight, vector<int64_t> &dp, vector<size_t> &indices, size_t depth=0 ) { if (depth == funcs.size()) { size_t ub=tight? 9:(number[pos]-'0'); for (size_t d=0; d<=ub; ++d) { size_t next=pos+1, prev=pos; (next <<= 1) |= (tight || d < ub); (prev <<= 1) |= tight; 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[depth]=0; indices[depth]<ubs[depth]; ++indices[depth]) modify_table(number, pos, tight, dp, indices, depth+1); } template <class Satisfies> pair<int64_t, int64_t> count_up(Satisfies satisfies) { vector<size_t> indices(funcs.size()); pair<int64_t, int64_t> res; count_up(indices, satisfies, res); return res; } template <class Satisfies> void count_up( vector<size_t> &indices, Satisfies satisfies, pair<int64_t, int64_t> &res, size_t depth=0 ) { if (depth == indices.size()) { if (!satisfies(indices)) return; size_t lt=(n<<1), eq=(n<<1|1); for (size_t i=0; i<depth; ++i) { (lt *= ubs[i]) += indices[i]; (eq *= ubs[i]) += indices[i]; } (res.first += dp[eq]) %= mod; (res.second += dp[eq] + dp[lt]) %= mod; return; } for (indices[depth]=0; indices[depth]<ubs[depth]; ++indices[depth]) count_up(indices, satisfies, res, depth+1); } }; int64_t count(const string &A, const string &B, 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; }); int64_t res=0; auto satisfies=[](const vector<size_t> &v)->bool { return (v[0] || v[1] == 0) && v[2] != 0; }; d.store(B); res += d.count_up(satisfies).second; d.store(A); res -= d.count_up(satisfies).first; return (res += 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; }