QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#290557#6780. 矩阵游戏MoRanSky100 ✓482ms17192kbC++232.1kb2023-12-25 05:49:142023-12-25 05:49:14

Judging History

你现在查看的是最新测评结果

  • [2023-12-25 05:49:14]
  • 评测
  • 测评结果:100
  • 用时:482ms
  • 内存:17192kb
  • [2023-12-25 05:49:14]
  • 提交

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