QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#581026 | #7775. 【模板】矩阵快速幂 | nhuang685 | 25 | 1316ms | 215988kb | C++23 | 6.8kb | 2024-09-22 04:36:47 | 2024-09-22 04:36:47 |
Judging History
answer
/**
* @author n685
* @brief
* @date 2024-09-20 21:20:01
*
*
*/
#include "bits/stdc++.h"
#ifdef LOCAL
#include "dd/debug.h"
#else
#define dbg(...) 42
#define dbg_proj(...) 420
#define dbg_rproj(...) 420420
void nline() {}
void bar() {}
void start_clock() {}
void end_clock() {}
#endif
using i128 = __int128_t;
namespace rs = std::ranges;
namespace rv = std::views;
constexpr int MOD = 998'244'353;
template <class T>
concept integral = std::integral<T> || std::is_same_v<T, i128>;
struct BigInt {
static constexpr int BASE = 1000;
std::vector<int> digits;
BigInt() = default;
explicit BigInt(integral auto val) {
while (val > 0) {
digits.push_back(val % BASE);
val /= BASE;
}
}
explicit BigInt(std::string s) {
// for (char c : s | rv::reverse) {
// digits.push_back(c - '0');
// }
std::reverse(s.begin(), s.end());
s.resize((s.size() + 2) / 3 * 3, '0');
for (int i = 0; i < std::ssize(s); i += 3) {
digits.push_back(
100 * (s[i + 2] - '0') + 10 * (s[i + 1] - '0') + (s[i] - '0')
);
}
}
void trim() {
while (!digits.empty() && digits.back() == 0) {
digits.pop_back();
}
}
void carry() {
for (int i = 0; i < std::ssize(digits); ++i) {
if (digits[i] < BASE) {
continue;
}
if (i == std::ssize(digits) - 1) {
digits.push_back(0);
}
digits[i + 1] += digits[i] / BASE;
digits[i] %= BASE;
}
}
// value needs to be nonnegative
void deneg() {
for (int i = 0; i < std::ssize(digits) - 1; ++i) {
if (digits[i] >= 0) {
continue;
}
int val = ((BASE - 1) - digits[i]) / BASE;
digits[i + 1] -= val;
digits[i] += BASE * val;
}
trim();
}
BigInt &operator+=(const BigInt &rhs) {
digits.resize(std::max(digits.size(), rhs.digits.size()));
for (int i = 0; i < std::min(std::ssize(digits), std::ssize(rhs.digits));
++i)
{
digits[i] += rhs.digits[i];
}
carry();
return *this;
}
BigInt &operator-=(const BigInt &rhs) {
assert(digits.size() >= rhs.digits.size());
for (int i = 0; i < std::ssize(rhs.digits); ++i) {
digits[i] -= rhs.digits[i];
}
deneg();
return *this;
}
BigInt operator*(const BigInt &rhs) {
if (digits.empty() || rhs.digits.empty()) {
return BigInt{};
}
BigInt ans;
ans.digits.resize(digits.size() + rhs.digits.size() - 1);
for (int i = 0; i < std::ssize(digits); ++i) {
for (int j = 0; j < std::ssize(rhs.digits); ++j) {
ans.digits[i + j] += digits[i] * rhs.digits[j];
}
}
ans.carry();
ans.trim();
return ans;
}
std::pair<BigInt, int> div(int rhs) const {
BigInt ans;
int rem = 0;
for (int i : digits | rv::reverse) {
rem = rem * BASE + i;
ans.digits.push_back(rem / rhs);
rem %= rhs;
}
rs::reverse(ans.digits);
return {ans, rem};
}
int operator%(int rhs) const {
int val = 0;
for (int i : digits | rv::reverse) {
val
= static_cast<int>((static_cast<int64_t>(val) * BASE % rhs + i) % rhs);
}
return val;
}
bool operator==(const BigInt &rhs) const = default;
bool operator!=(const BigInt &rhs) const = default;
auto operator<=>(const BigInt &rhs) const {
if (digits.size() != rhs.digits.size()) {
return digits.size() <=> rhs.digits.size();
}
for (int i = static_cast<int>(digits.size()) - 1; i >= 0; --i) {
if (digits[i] != rhs.digits[i]) {
return digits[i] <=> rhs.digits[i];
}
}
return std::strong_ordering::equal;
}
};
BigInt operator+(BigInt a, const BigInt &b) { return a += b; }
BigInt operator-(BigInt a, const BigInt &b) { return a -= b; }
const BigInt BIGINF{std::string(100, '9')};
template <class T> constexpr T INF = T{};
template <std::floating_point T>
constexpr T INF<T> = std::numeric_limits<T>::infinity();
template <> constexpr int INF<int> = 0x3f3f3f3f; // 1061109567
template <>
constexpr int64_t INF<int64_t> = 0x3f3f3f3f3f3f3f3f; // 4557430888798830399
template <>
constexpr i128 INF<i128> = (static_cast<i128>(INF<int64_t>) << 64)
| INF<int64_t>; // 84069761239290679208598432424319205183
struct Edge {
int u, v;
i128 w;
};
void solve() {
static_assert(integral<i128>);
int n, m;
std::string sk;
std::cin >> n >> m >> sk;
BigInt k(sk);
std::vector<Edge> edges(m);
for (auto &[u, v, w] : edges) {
int64_t ww;
std::cin >> u >> v >> ww;
--u;
--v;
w = ww;
}
std::vector dist(n + 1, std::vector(n, std::vector<i128>(n, INF<i128>)));
std::vector d0(2 * n * n + 1, std::vector<i128>(n, INF<i128>));
d0[0][0] = 0;
for (int i = 0; i < n; ++i) {
dist[0][i][i] = 0;
}
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < n; ++j) {
for (auto &[u, v, w] : edges) {
dist[i][j][v] = std::min(dist[i][j][v], dist[i - 1][j][u] + w);
}
}
d0[i] = dist[i][0];
}
for (int i = n + 1; i <= 2 * n * n; ++i) {
for (auto &[u, v, w] : edges) {
d0[i][v] = std::min(d0[i][v], d0[i - 1][u] + w);
}
}
if (k <= BigInt{2 * n * n}) {
int kk = std::stoi(sk);
for (int i = 0; i < n; ++i) {
if (d0[kk][i] == INF<i128>) {
std::cout << "-1 ";
} else {
std::cout << static_cast<int>(d0[kk][i] % MOD) << ' ';
}
}
std::cout << '\n';
return;
}
std::vector dp(n * n + 1, std::vector<BigInt>(n, BIGINF));
for (int i = 0; i < n; ++i) {
i128 mi = INF<i128> / n;
int sz = 1;
for (int j = 1; j <= n; ++j) {
if (dist[j][i][i] != INF<i128> && dist[j][i][i] * sz < mi * j) {
mi = dist[j][i][i];
sz = j;
}
}
if (mi == INF<i128> / n) {
continue;
}
for (int j = 0; j <= n * n; ++j) {
if (d0[j][i] == INF<i128>) {
continue;
}
auto [times, rem] = (k - BigInt{j + n * n}).div(sz);
int rest = n * n;
if (rem > 0) {
times += BigInt{1};
rest -= sz - rem;
}
BigInt res = times * BigInt{mi} + BigInt{d0[j][i]};
dp[rest][i] = std::min(dp[rest][i], res);
}
}
for (int i = n * n - 1; i >= 0; --i) {
for (auto [u, v, w] : edges) {
dp[i][v] = std::min(dp[i][v], dp[i + 1][u] + BigInt{w});
}
}
for (int i = 0; i < n; ++i) {
if (dp[0][i] == BIGINF) {
std::cout << "-1 ";
} else {
std::cout << dp[0][i] % MOD << ' ';
}
}
std::cout << '\n';
}
int main() {
#ifndef LOCAL
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
#endif
int s, t;
std::cin >> s >> t;
for (int i = 0; i < t; ++i) {
dbg(i + 1);
solve();
bar();
}
}
詳細信息
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 570ms
memory: 215988kb
input:
1 1 100 101 899539897889989959 74 35 910832669819965536 35 85 910832669819965536 85 88 910832669819965536 88 30 910832669819965536 30 58 910832669819965536 58 60 910832669819965536 60 34 910832669819965536 34 8 910832669819965536 8 67 910832669819965536 67 89 910832669819965536 89 32 910832669819965...
output:
395495792 395495781 395495783 395495839 395495793 395495789 395495754 395495832 395495845 395495755 395495823 395495773 395495753 395495800 395495782 395495763 395495847 395495761 395495794 395495791 395495786 395495821 395495798 395495765 395495772 395495770 395495757 395495819 395495843 395495828 ...
result:
ok 100 numbers
Test #2:
score: 10
Accepted
time: 996ms
memory: 215868kb
input:
1 1 100 200 998858598565699977 89 61 596014036562538539 89 84 921297646113897322 61 84 946923234442637386 61 35 641628261157284465 84 35 979893473772327497 84 78 700172488379560611 35 78 963617193748189613 35 54 951598888254521423 78 54 680825215292116806 78 21 737055858973038555 54 21 7491794406112...
output:
590375247 265938345 203065828 597548045 369717762 226160283 377877020 360218254 956162456 408060901 387231165 759578975 67601808 790211315 608425007 343195480 177353482 436533546 717630459 417099733 542227025 861764246 913806375 587268602 989846681 435016550 66609901 817090566 256847656 844441854 94...
result:
ok 100 numbers
Test #3:
score: 10
Accepted
time: 952ms
memory: 215848kb
input:
1 1 100 181 348568663892999968 25 19 990622898175774733 19 94 871060999389241529 94 24 969317630558501400 24 43 908457844888427461 43 52 816088481082287266 52 62 978618931332609685 62 99 761714433396732044 99 85 741344935503895668 85 64 964684335126604843 64 69 988098065125373655 69 31 7506975506815...
output:
916998469 916998469 916998469 76035207 62461893 916998469 389136594 916998469 916998469 173423529 164423356 822964468 626456020 916998469 744111524 916998469 398953850 916998469 342238577 916998469 255074799 784015663 916998469 740933556 587088671 811719512 916998469 916998469 916998469 916998469 14...
result:
ok 100 numbers
Test #4:
score: 10
Accepted
time: 962ms
memory: 215880kb
input:
1 1 100 189 295064635124730243 18 50 754672892083203214 50 88 962632394366987404 88 15 906700334097319336 15 26 967741400981618572 26 91 996214498763867892 91 35 882157548994344280 35 68 983621159612138407 68 51 563935036482744182 51 75 991205513962219551 75 72 974025375183814852 72 11 7979447663592...
output:
663199381 739882534 663199381 28600701 663199381 944601671 836329160 894091561 629507606 663199381 246830507 663199381 491987421 663199381 802123884 663199381 663199381 663199381 414785533 989396289 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 663199381 4...
result:
ok 100 numbers
Test #5:
score: 10
Accepted
time: 545ms
memory: 16868kb
input:
1 254 40 74 997173688939799978 38 6 890721839505665075 6 10 992308491267087930 10 29 960202932780090595 29 20 952827125924298715 20 34 868314670055961466 34 31 756448635709788087 31 14 857625921909632516 14 18 917667459973696862 18 21 985939328882662624 21 1 734882468602343649 1 11 66102593854575036...
output:
177014577 177014577 177014577 885341552 472856470 177014577 363547548 177014577 499847464 653076748 177014577 177014577 177014577 177014577 487939796 177014577 213466543 586729345 244952763 177014577 177014577 177014577 177014577 890105934 177014577 177014577 890105934 177014577 177014577 798890006 ...
result:
ok 3575 numbers
Test #6:
score: 10
Accepted
time: 541ms
memory: 10200kb
input:
1 356 32 47 967844399484634837 4 30 776954643355911997 30 20 811634053140142741 20 22 747630229183579429 22 2 806282875388761050 2 26 719793351534499411 26 17 797537828929335673 17 24 890423236992687627 24 21 970792227007588899 21 8 850078803097295262 8 15 958474507028658347 15 1 972636122087215360 ...
output:
890097469 525779071 636798453 776362497 776362497 687961593 158033324 776362497 345910504 380622623 239804834 440670451 137231885 985041116 222869127 137231885 705696901 637534644 347889826 696528073 291555427 146553026 776362497 624486185 137231885 642408114 520519927 137231885 438373632 263924254 ...
result:
ok 4784 numbers
Subtask #2:
score: 0
Time Limit Exceeded
Test #7:
score: 0
Time Limit Exceeded
input:
2 1 300 598 8179377797889487867988994778539839593376697796496698959964978969 1 2 977880533270721156 2 1 977880533270721156 2 3 977880533270721156 3 2 977880533270721156 3 4 977880533270721156 4 3 977880533270721156 4 5 977880533270721156 5 4 977880533270721156 5 6 977880533270721156 6 5 977880533270...
output:
result:
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 15
Accepted
Dependency #1:
100%
Accepted
Test #19:
score: 15
Accepted
time: 700ms
memory: 215900kb
input:
4 1 100 101 6888995999928874698772868926699656683388498575797893294688976887 25 90 495511874996847106 90 84 495511874996847106 84 82 495511874996847106 82 40 495511874996847106 40 97 495511874996847106 97 5 495511874996847106 5 24 495511874996847106 24 16 495511874996847106 16 19 495511874996847106 ...
output:
662900138 662900131 662900188 662900147 662900176 662900221 662900152 662900202 662900130 662900140 662900169 662900199 662900128 662900145 662900192 662900178 662900163 662900150 662900179 662900151 662900139 662900180 662900216 662900177 662900170 662900205 662900210 662900183 662900184 662900125 ...
result:
ok 100 numbers
Test #20:
score: 15
Accepted
time: 1316ms
memory: 215872kb
input:
4 1 100 200 7298898492397999688666927949888498969897838287679988999656889979 1 68 716477084362826727 1 70 849254955511480878 68 70 965501875328180109 68 27 922798232695217800 70 27 973650788054328171 70 69 992887836560799260 27 69 912347321604310534 27 41 707737334645887057 69 41 939222694708421463 ...
output:
59219241 402083566 593666306 414807498 258758770 177911843 190858821 427609509 714942754 794670437 266523695 250908431 280340515 973300594 490891479 435411914 570632298 806776572 581872834 661756417 571008187 273666813 634277068 321782154 962526931 884883598 912195600 389101189 783089343 302322065 7...
result:
ok 100 numbers
Test #21:
score: 15
Accepted
time: 1246ms
memory: 215928kb
input:
4 1 100 170 8794888769994978795934858981288869698995675273759827929988816678 85 25 955229927087338794 25 69 715916767824027774 69 8 871119978520194455 8 64 918533454985251428 64 73 928715673496434787 73 95 777734955942460360 95 82 937506435422061091 82 21 972958971354009576 21 81 920481916656974333 ...
output:
1429581 1429581 150584952 1429581 1429581 616522075 1429581 1429581 56697037 26641870 455335474 405458157 1429581 119209248 768006956 56697037 1429581 1429581 56697037 825267652 337654936 589008244 691024955 410854366 1429581 1429581 569334223 757829937 1429581 1429581 1429581 387845353 1429581 1429...
result:
ok 100 numbers
Test #22:
score: 15
Accepted
time: 930ms
memory: 215824kb
input:
4 1 100 175 988927424060208873 73 39 871487671517176049 39 12 989592888976857487 12 60 753594598459115125 60 80 804510907944284786 80 87 837728552224523957 87 50 720829671677245259 50 55 955472566241448463 55 56 698073335743612454 56 24 907173313658798936 24 75 812098650937527351 75 23 9749473294852...
output:
120476850 665961545 406533341 950211937 665961545 665961545 665961545 160438797 665961545 860608848 665961545 665961545 665961545 665961545 698344451 665961545 115173142 157625083 665961545 665961545 665961545 817070036 795455857 665961545 615381143 665961545 363716660 579107160 665961545 665961545 ...
result:
ok 100 numbers
Test #23:
score: 15
Accepted
time: 599ms
memory: 17192kb
input:
4 272 40 69 8526848846996917979164958976967645898953979497989749477999798947 16 20 904311791006766339 20 8 861881272650260368 8 38 927651150818983482 38 22 575472375470752507 22 10 995789624005306013 10 17 862458045607914444 17 35 910173488885856948 35 12 897609723109586512 12 23 970232607197909774 ...
output:
631006282 189710405 538148249 980737927 538148249 223767537 200756370 844883815 538148249 538148249 506622768 538148249 278823150 381947526 538148249 594558624 538148249 751430936 664913832 538148249 961366366 945739792 646619933 538148249 538148249 538148249 538148249 831302 107422344 538148249 118...
result:
ok 3782 numbers
Test #24:
score: 15
Accepted
time: 578ms
memory: 10252kb
input:
4 367 32 64 7694675676969676989727597922979586548768678479696836977677459878 26 1 948535512091890169 1 28 927579818325689242 28 18 869862583518920980 18 24 916474447302009020 24 23 592009716422157884 23 12 932781568469333631 12 17 906790845067818370 17 16 733495190715963829 16 5 948217995091033642 5...
output:
242947009 937164220 269122924 473901869 812915310 815200847 138502251 269122924 269122924 269122924 269122924 269122924 269122924 790732730 269122924 269122924 423399215 858100602 269122924 259562134 269122924 613550676 269122924 242947009 269122924 269122924 210817778 269122924 269122924 269122924 ...
result:
ok 4886 numbers
Subtask #5:
score: 0
Time Limit Exceeded
Dependency #1:
100%
Accepted
Test #25:
score: 0
Time Limit Exceeded
input:
5 1 300 301 969767789936486493 164 284 964646444984408140 284 241 964646444984408140 241 281 964646444984408140 281 138 964646444984408140 138 242 964646444984408140 242 112 964646444984408140 112 217 964646444984408140 217 170 964646444984408140 170 31 964646444984408140 31 300 964646444984408140 3...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #3:
0%