QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#290557 | #6780. 矩阵游戏 | MoRanSky | 100 ✓ | 482ms | 17192kb | C++23 | 2.1kb | 2023-12-25 05:49:14 | 2023-12-25 05:49:14 |
Judging History
answer
// Skyqwq
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef pair<int, int> PII;
typedef long long LL;
template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; }
template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; }
template <typename T> void inline read(T &x) {
int f = 1; x = 0; char s = getchar();
while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); }
while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar();
x *= f;
}
const int P = 1e9 + 7, N = 1e6 + 5;
char s[N], t[N];
int a, b, c, d;
void inline add(int &x, int y) {
x += y;
if (x >= P) x -= P;
}
struct Mat{
int w[2][2], n, m;
Mat operator * (const Mat &b) const {
Mat c; memset(c.w, 0, sizeof c.w);
c.n = n, c.m = b.m;
for (int i = 0; i < n; i++)
for (int j = 0; j < b.m; j++)
for (int k = 0; k < m; k++) {
add(c.w[i][j], 1ll * w[i][k] * b.w[k][j] % P);
}
return c;
}
} A, B, ret;
vector<int> S, T;
void inline wk(vector<int> &x) {
reverse(x.begin(), x.end());
int t = 0;
x[0] -= 1;
for (int i = 0; i < x.size(); i++) {
if (x[i] < 0) x[i] += 10, x[i + 1] -= 1;
}
}
Mat dw() {
Mat ret; ret.n = ret.m = 2;
memset(ret.w, 0, sizeof ret.w);
ret.w[0][0] = ret.w[1][1] = 1;
return ret;
}
Mat inline pw(Mat a, vector<int> b) {
Mat ret = dw();
for (int v: b) {
for (int i = 0; i < v; i++) ret = ret * a;
Mat zz = a * a;
Mat pp = zz * zz;
a = (pp * pp) * zz;
}
return ret;
}
int main() {
scanf("%s%s", s + 1, t + 1);
for (int i = 1; s[i]; i++) S.pb(s[i] - '0');
for (int i = 1; t[i]; i++) T.pb(t[i] - '0');
wk(S), wk(T);
read(a), read(b), read(c), read(d);
A.n = A.m = B.n = B.m = 2;
A.w[1][1] = B.w[1][1] = 1;
A.w[0][0] = a, A.w[1][0] = b;
B.w[0][0] = c, B.w[1][0] = d;
ret.n = 1, ret.m = 2;
ret.w[0][0] = ret.w[0][1] = 1;
A = pw(A, T);
B = B * A;
B = pw(B, S);
ret = ret * A;
ret = ret * B;
printf("%d\n", ret.w[0][0]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 5
Accepted
time: 0ms
memory: 3864kb
input:
5 8 538 564 544 554
output:
734404709
result:
ok 1 number(s): "734404709"
Test #2:
score: 5
Accepted
time: 0ms
memory: 3796kb
input:
76 57 747 553 512 587
output:
509062872
result:
ok 1 number(s): "509062872"
Test #3:
score: 5
Accepted
time: 0ms
memory: 3868kb
input:
993 515 599047507 609785818 539754462 539620194
output:
160458773
result:
ok 1 number(s): "160458773"
Test #4:
score: 5
Accepted
time: 0ms
memory: 3840kb
input:
824 625 827310097 593656432 547704115 541664982
output:
20983662
result:
ok 1 number(s): "20983662"
Test #5:
score: 5
Accepted
time: 0ms
memory: 3748kb
input:
785606791 582520213 794287318 517754367 794287318 517754367
output:
827514987
result:
ok 1 number(s): "827514987"
Test #6:
score: 5
Accepted
time: 0ms
memory: 3840kb
input:
551764325 552672618 1 552552870 1 671779128
output:
72536129
result:
ok 1 number(s): "72536129"
Test #7:
score: 5
Accepted
time: 0ms
memory: 3872kb
input:
562999645 549501442 521163543 587647809 559038878 563565326
output:
297915726
result:
ok 1 number(s): "297915726"
Test #8:
score: 5
Accepted
time: 0ms
memory: 3840kb
input:
799151735 795439382 826383159 511493177 593206386 987956809
output:
446789096
result:
ok 1 number(s): "446789096"
Test #9:
score: 5
Accepted
time: 0ms
memory: 3856kb
input:
959802787 540508766 557573504 865420191 591656177 891159072
output:
580597374
result:
ok 1 number(s): "580597374"
Test #10:
score: 5
Accepted
time: 0ms
memory: 3860kb
input:
568806419 976652351 820723356 571190676 511826428 811486013
output:
191253349
result:
ok 1 number(s): "191253349"
Test #11:
score: 5
Accepted
time: 1ms
memory: 3932kb
input:
915891339567783719418542075931928518008894859587019918304183031123402449058633865118848488252702169619825453782091128361926628644276086352709934237593742696600352874045043600714434995715542145092073502833156505467592658132078543593336790670688105246151328440361190475753594962894421123922243652814192...
output:
406979648
result:
ok 1 number(s): "406979648"
Test #12:
score: 5
Accepted
time: 1ms
memory: 3868kb
input:
775573305497471351945732884369534081088904114291268171478295422987322428446961026183476905672375287939012033381254015119380347311583769393339516436912036969811315207193324367212225091490575513267198604381108212961621674339797949047148641532710507318621188991687891486540401170950781269352201271893848...
output:
23217418
result:
ok 1 number(s): "23217418"
Test #13:
score: 5
Accepted
time: 1ms
memory: 3756kb
input:
860982691349726688278220054291748021644556626495469174023165056341812248459530941423598882859657577685629854780820556486211559714296056218683310870718036735882855284529949741445768777670038028923881276630715229380342043237080578273850231281279605942383657986093319856638505753084940514731430611194208...
output:
106080151
result:
ok 1 number(s): "106080151"
Test #14:
score: 5
Accepted
time: 1ms
memory: 3756kb
input:
795548083670632888389282067028889380489980073941278263721664650714525456021398303196714738464080351505378862681650409086849239011729012889957788497117712082777306653217866978707835635481421218988653926670681416169052815616326070165540644565489376406913968435939931070021131131384462555545555678121419...
output:
894048159
result:
ok 1 number(s): "894048159"
Test #15:
score: 5
Accepted
time: 7ms
memory: 4024kb
input:
505817731500505884622037277552833842839513966659507687813532649296689473231749140842266291901915817283525465244221607933271081322010543724385385190378076959544969084420949750049870678624912667323148535140207848613719859626453893715777411431161896714265730724192287768660219958429629037521515312265053...
output:
557680189
result:
ok 1 number(s): "557680189"
Test #16:
score: 5
Accepted
time: 6ms
memory: 4092kb
input:
542875439655077482559669156504001111155061573538351628289906077614437097607425583313024576925398145278634645539265978981672924240987902549212943908253650580973029979722824857544145590508947175740811639681816315276000521968870129264203021998236894041291087319688123196754107708597785774039320153412328...
output:
987263402
result:
ok 1 number(s): "987263402"
Test #17:
score: 5
Accepted
time: 298ms
memory: 17192kb
input:
732246221301106053080219382860111771119011446742518981985652242222749494299672222907780911542708402136467460576671025846260354487710229407444261963251936491486294324698149815136708456101816944584162009935100912934678965165558926014501922482490173631953094676044003789125303724835964973296648173111388...
output:
168098285
result:
ok 1 number(s): "168098285"
Test #18:
score: 5
Accepted
time: 297ms
memory: 17108kb
input:
661942977430476555937871955216529850952667399890763942856308314229841076605608608234144619383205400032175420335448123256630692330065732446134841385430615348037758135884646471678639890102201958385981753408760521591173537247083669708873930961908055343942746703958109775710817347303464659404875938982194...
output:
109587766
result:
ok 1 number(s): "109587766"
Test #19:
score: 5
Accepted
time: 297ms
memory: 16992kb
input:
622949269104327171246660145966592918728295529170312733226412949245311414614205043791496528842696798124918074658612770935735242451312996187440481764679619765608179766176969090792850378626707601880053129768175898215826943209504851932069987093889270859218813890051109971516975129301043208246533333425161...
output:
874855463
result:
ok 1 number(s): "874855463"
Test #20:
score: 5
Accepted
time: 482ms
memory: 17184kb
input:
100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
589804924
result:
ok 1 number(s): "589804924"
Extra Test:
score: 0
Extra Test Passed