QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#622869 | #8795. Mysterious Sequence | rns_phn# | AC ✓ | 1ms | 4032kb | C++14 | 3.1kb | 2024-10-09 08:07:06 | 2024-10-09 08:07:08 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
using namespace std;
using Z = double; // not necessary, maybe MINT
struct Mat { // 0-based index
vector<vector<Z>> a;
static int D;
const static void setD(int _D) {
D = _D;
}
Mat(int k = 0) {
a.assign(D, vector<Z>(D, 0));
for (int i = 0; i < D; i++)
a[i][i] = k;
}
Mat operator+(const Mat &x) {
Mat res;
for (int i = 0; i < D; i++)
for (int j = 0; j < D; j++)
res.a[i][j] = a[i][j] + x.a[i][j];
return res;
}
Mat operator-(const Mat &x) {
Mat res;
for (int i = 0; i < D; i++)
for (int j = 0; j < D; j++)
res.a[i][j] = a[i][j] - x.a[i][j];
return res;
}
Mat operator*(const Mat &x) {
Mat res;
for (int i = 0; i < D; i++)
for (int j = 0; j < D; j++)
for (int k = 0; k < D; k++)
res.a[i][j] += a[i][k] * x.a[k][j];
return res;
}
Mat pow(long long k) {
Mat res = Mat(1), b = *this;
for (; k; k >>= 1) {
if (k & 1) res = res * b;
b = b * b;
}
return res;
}
friend istream &operator>>(istream &stream, Mat &M) {
for (int i = 0; i < D; i++) {
for (int j = 0; j < D; j++) {
stream >> M.a[i][j];
}
}
return stream;
}
friend ostream &operator<<(ostream &stream, const Mat &M) {
for (int i = 0; i < D; i++) {
for (int j = 0; j < D; j++) {
if (j) stream << ' ';
stream << M.a[i][j];
}
stream << '\n';
}
return stream;
}
Z det() {
vector<vector<Z>> work(D, vector<Z>(D, 0));
Z rlt = 1;
for (int i = 0; i < D; i++)
for (int j = 0; j < D; j++)
work[i][j] = a[i][j];
for (int i = 0; i < D; i++) {
for (int ii = i + 1; ii < D; ii++) {
if (work[ii][i] != 0) {
Z tmp = work[i][i] / work[ii][i];
for (int j = i; j < D; j++)
work[i][j] -= work[ii][j] * tmp;
for (int j = i; j < D; j++)
swap(work[i][j], work[ii][j]);
rlt *= -1;
}
}
if (work[i][i] == 0) return 0;
rlt *= work[i][i];
}
return rlt;
}
};
int Mat::D = 2;
signed main() {
double A, B;
int n, x1, xn;
cin >> A >> B;
cin >> n >> x1 >> xn;
Mat a;
a.a[0][0] = A;
a.a[0][1] = B;
a.a[1][0] = 1;
a.a[1][1] = 0;
Mat c = a.pow(n - 2);
vector<double> x(n + 1, 0);
x[1] = x1, x[n] = xn;
x[2] = (xn - c.a[0][1] * x1) / c.a[0][0];
for (int i = 3; i < n; i++) {
x[i] = x[i - 1] * A + x[i - 2] * B;
}
cout << fixed << setprecision(15);
for (int i = 1; i <= n; i++)
cout << x[i] << endl;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3788kb
input:
1.0 1.0 10 1 10
output:
1.000000000000000 -0.323529411764706 0.676470588235294 0.352941176470588 1.029411764705882 1.382352941176471 2.411764705882353 3.794117647058824 6.205882352941178 10.000000000000000
result:
ok 10 numbers
Test #2:
score: 0
Accepted
time: 1ms
memory: 3796kb
input:
1 1 2 1 100
output:
1.000000000000000 100.000000000000000
result:
ok 2 numbers
Test #3:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
1 1 5 50 100
output:
50.000000000000000 0.000000000000000 50.000000000000000 50.000000000000000 100.000000000000000
result:
ok 5 numbers
Test #4:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
0.25 0.25 10 1 1
output:
1.000000000000000 55.875536480686698 14.218884120171674 17.523605150214593 7.935622317596566 6.364806866952790 3.575107296137339 2.484978540772532 1.515021459227468 1.000000000000000
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
0.25 0.63 6 93 12
output:
93.000000000000000 -14.204807958665043 55.038798010333743 4.810670488624458 35.877110368666372 12.000000000000000
result:
ok 6 numbers
Test #6:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
0.25 0.80 10 5 63
output:
5.000000000000000 78.769536183531329 23.692384045882832 68.938724958295779 36.188588476280216 64.198127085706687 45.000402552450851 62.608602306678065 51.652472618630199 63.000000000000000
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
0.25 0.99 3 18 30
output:
18.000000000000000 48.719999999999999 30.000000000000000
result:
ok 3 numbers
Test #8:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
0.28 0.64 9 6 10
output:
6.000000000000000 20.950403348507802 9.706112937582185 16.125969765568005 10.727183814411640 13.324232117998783 10.596182634263108 11.494439693112891 10.000000000000000
result:
ok 9 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 4032kb
input:
0.31 0.40 7 10 49
output:
10.000000000000000 240.115063998688214 78.435669839593345 120.361083249749214 68.686203743259597 69.437156460310163 49.000000000000000
result:
ok 7 numbers
Test #10:
score: 0
Accepted
time: 0ms
memory: 3960kb
input:
0.32 0.28 5 36 6
output:
36.000000000000000 10.121376811594200 13.318840579710146 7.096014492753623 6.000000000000000
result:
ok 5 numbers
Test #11:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
0.35 0.65 10 86 82
output:
86.000000000000000 79.533924786230855 83.736873675180789 81.004956897363328 82.780702802944674 81.626467964316802 82.376720609424922 81.889056390104642 82.206038132662826 82.000000000000000
result:
ok 10 numbers
Test #12:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
0.36 0.68 8 72 59
output:
72.000000000000000 38.239918642605666 62.726370711338042 48.584638133053545 60.144401811609143 54.689538582655700 60.586427121650274 59.000000000000000
result:
ok 8 numbers
Test #13:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
0.43 0.61 2 93 84
output:
93.000000000000000 84.000000000000000
result:
ok 2 numbers
Test #14:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
0.46 0.96 6 65 35
output:
65.000000000000000 -16.617423662818045 54.755985115103698 9.235026436642380 56.813857871355040 35.000000000000000
result:
ok 6 numbers
Test #15:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
0.50 0.90 4 19 1
output:
19.000000000000000 -6.565217391304349 13.817391304347828 1.000000000000000
result:
ok 4 numbers
Test #16:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
0.54 0.35 3 16 22
output:
16.000000000000000 30.370370370370367 22.000000000000000
result:
ok 3 numbers
Test #17:
score: 0
Accepted
time: 0ms
memory: 3892kb
input:
0.55 0.89 10 74 13
output:
74.000000000000000 -48.321937076576532 39.282934607882908 -21.400909963817512 23.191311320916157 -6.291588641293698 17.179893322903848 3.849427436845725 17.407290147649576 13.000000000000000
result:
ok 10 numbers
Test #18:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
0.56 0.36 3 31 88
output:
31.000000000000000 137.214285714285694 88.000000000000000
result:
ok 3 numbers
Test #19:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
0.57 0.93 7 71 48
output:
71.000000000000000 -34.080565361686020 46.604077743838971 -5.130601472379787 40.417349462513769 18.266429824319644 48.000000000000000
result:
ok 7 numbers
Test #20:
score: 0
Accepted
time: 0ms
memory: 3828kb
input:
0.58 0.41 8 30 69
output:
30.000000000000000 89.432121682809850 64.170630576029708 73.886135624049274 69.163917198120757 70.408387580770238 69.194070848076237 69.000000000000000
result:
ok 8 numbers
Test #21:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
0.58 0.49 6 31 96
output:
31.000000000000000 99.557613538417172 72.933415852281954 91.084611828147956 88.566448627943970 96.000000000000000
result:
ok 6 numbers
Test #22:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
0.61 0.29 8 62 25
output:
62.000000000000000 34.407651257133736 38.968667266851583 33.749105897348251 31.887868104769392 29.238840254140321 27.083174305408718 25.000000000000000
result:
ok 8 numbers
Test #23:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
0.63 0.89 9 37 85
output:
37.000000000000000 -5.887853302176884 29.220652419628564 13.168821585428567 34.302738252289416 33.330976309973757 51.527952119821052 62.127178751363907 85.000000000000000
result:
ok 9 numbers
Test #24:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
0.64 0.67 2 74 42
output:
74.000000000000000 42.000000000000000
result:
ok 2 numbers
Test #25:
score: 0
Accepted
time: 0ms
memory: 3956kb
input:
0.65 0.56 2 94 96
output:
94.000000000000000 96.000000000000000
result:
ok 2 numbers
Test #26:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
0.65 0.90 10 97 23
output:
97.000000000000000 -61.703576279117563 47.192675418573579 -24.857979629132981 26.315721117779784 -5.266962939662822 20.260623095220971 8.429138366197092 23.713500723726984 23.000000000000000
result:
ok 10 numbers
Test #27:
score: 0
Accepted
time: 0ms
memory: 3736kb
input:
0.67 0.88 4 70 42
output:
70.000000000000000 0.547821506509144 61.967040409361125 42.000000000000000
result:
ok 4 numbers
Test #28:
score: 0
Accepted
time: 0ms
memory: 3792kb
input:
0.69 0.39 10 2 27
output:
2.000000000000000 22.365907687016136 16.212476304041132 19.909312647724676 20.060291485506067 21.606233057611810 22.731814489099513 24.111382889947269 25.502261844812423 27.000000000000000
result:
ok 10 numbers
Test #29:
score: 0
Accepted
time: 1ms
memory: 3920kb
input:
0.69 0.57 4 88 47
output:
88.000000000000000 11.843609597552826 58.332090622311448 47.000000000000000
result:
ok 4 numbers
Test #30:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
0.71 0.89 8 4 41
output:
4.000000000000000 6.838890362691074 8.415612157510662 12.061697054627626 16.053699728970102 22.133037186187359 30.002249160976415 41.000000000000000
result:
ok 8 numbers
Test #31:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
0.72 0.49 8 21 48
output:
21.000000000000000 19.940442369940303 24.647118506357018 27.516742085847799 31.889142369925352 36.443386128411674 41.864917773719824 48.000000000000000
result:
ok 8 numbers
Test #32:
score: 0
Accepted
time: 0ms
memory: 3928kb
input:
0.74 0.58 3 57 29
output:
57.000000000000000 -5.486486486486480 29.000000000000000
result:
ok 3 numbers
Test #33:
score: 0
Accepted
time: 0ms
memory: 3860kb
input:
0.76 0.70 2 91 18
output:
91.000000000000000 18.000000000000000
result:
ok 2 numbers
Test #34:
score: 0
Accepted
time: 0ms
memory: 3740kb
input:
0.77 0.36 10 31 25
output:
31.000000000000000 5.214972085026424 15.175528505470346 13.562546899821680 15.906351374832017 17.130407442556457 18.916700225707999 20.732805853115483 22.774272588153803 25.000000000000000
result:
ok 10 numbers
Test #35:
score: 0
Accepted
time: 0ms
memory: 3952kb
input:
0.77 0.96 8 78 68
output:
78.000000000000000 -40.097557007604983 44.004881104144161 -4.609896277109783 38.695065726603858 25.369700183459582 56.681932238803583 68.000000000000000
result:
ok 8 numbers
Test #36:
score: 0
Accepted
time: 0ms
memory: 3796kb
input:
0.78 0.52 7 73 77
output:
73.000000000000000 8.727547506052931 44.767487054721286 39.456964605830130 54.055525661002576 62.680931610613683 77.000000000000000
result:
ok 7 numbers
Test #37:
score: 0
Accepted
time: 0ms
memory: 3920kb
input:
0.78 0.69 4 42 97
output:
42.000000000000000 57.297905113986445 73.672365988909434 97.000000000000000
result:
ok 4 numbers
Test #38:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
0.78 0.70 10 54 99
output:
54.000000000000000 -13.012886350899695 27.649948646298235 12.457939498482839 29.072156861225380 31.396840000693786 44.840045003398920 56.953023103136815 75.811389522825962 99.000000000000000
result:
ok 10 numbers
Test #39:
score: 0
Accepted
time: 0ms
memory: 3856kb
input:
0.78 0.76 10 97 83
output:
97.000000000000000 -43.734736959040482 39.606905171948419 -2.345014054751001 28.272136967975019 20.270056153409755 37.297467895320622 44.497267634941501 63.053944355698050 83.000000000000000
result:
ok 10 numbers
Test #40:
score: 0
Accepted
time: 0ms
memory: 4028kb
input:
0.78 0.95 10 100 32
output:
100.000000000000000 -63.269578817364120 45.649728522455987 -24.499311628980237 24.257779025728599 -4.353278407462916 19.649332916621095 11.190865187874685 27.395741117332292 32.000000000000000
result:
ok 10 numbers
Test #41:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
0.79 0.90 10 98 42
output:
98.000000000000000 -58.246914628041360 42.184937443847325 -19.096122584597836 22.880506857630301 0.889090091389885 21.294837344065282 17.623102584062472 33.087604651068105 42.000000000000000
result:
ok 10 numbers
Test #42:
score: 0
Accepted
time: 0ms
memory: 4016kb
input:
0.81 0.48 10 97 1
output:
97.000000000000000 -38.257501681599209 15.571423637904633 -5.750747660464864 2.816177741217683 -0.479254906636811 0.963568841408671 0.550448406355354 0.908376253023999 1.000000000000000
result:
ok 10 numbers
Test #43:
score: 0
Accepted
time: 0ms
memory: 3800kb
input:
0.81 0.86 10 20 100
output:
20.000000000000000 -3.332842869651405 14.500397275582362 8.879076925321506 19.662393966511249 23.562545268650609 35.995320478806669 49.419998518872930 70.986174412060805 100.000000000000000
result:
ok 10 numbers
Test #44:
score: 0
Accepted
time: 0ms
memory: 3748kb
input:
0.84 0.85 10 74 95
output:
74.000000000000000 -36.290804877098289 32.415723903237435 -3.617976066814098 24.514265421627975 17.516703297375514 35.551156378179215 44.752169160439728 67.810305016221704 95.000000000000000
result:
ok 10 numbers
Test #45:
score: 0
Accepted
time: 0ms
memory: 3924kb
input:
0.88 0.37 10 3 96
output:
3.000000000000000 29.021828490376414 26.649209071531246 34.189380524386770 39.946862217926920 47.803309545798797 56.847251420935898 67.712805782369145 80.620752114231124 96.000000000000000
result:
ok 10 numbers
Test #46:
score: 0
Accepted
time: 0ms
memory: 3908kb
input:
0.91 0.50 10 100 98
output:
100.000000000000000 -22.586857854484428 29.445959352419170 15.502394083459230 28.830158292157485 33.986641087592929 45.342922535788304 58.255380051363822 75.683857114635231 98.000000000000000
result:
ok 10 numbers
Test #47:
score: 0
Accepted
time: 0ms
memory: 3912kb
input:
0.94 0.48 10 44 97
output:
44.000000000000000 -1.582743438717800 19.632221167605266 17.694571046964406 26.056362944597065 32.986375270464151 43.514246967642890 56.736852279407103 74.219479687111260 97.000000000000000
result:
ok 10 numbers
Test #48:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
0.94 0.54 10 28 95
output:
28.000000000000000 0.452546307145841 15.545393528717092 14.857044922852818 22.360134732988879 29.041330907350066 39.373323808723057 52.693243070168712 70.793243342669030 95.000000000000000
result:
ok 10 numbers
Test #49:
score: 0
Accepted
time: 0ms
memory: 3812kb
input:
0.95 0.57 10 2 94
output:
2.000000000000000 9.227284174161062 9.905919965453009 14.670175946452163 19.583041529437772 26.965889742443615 36.779928927100961 50.311489633938777 68.760474640689381 94.000000000000000
result:
ok 10 numbers
Test #50:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
0.98 0.90 10 21 99
output:
21.000000000000000 -8.213193484970176 10.851070384729230 3.242174840561487 12.943294690006564 15.602386152711771 26.939303650663444 40.442665115090769 63.879185098386060 99.000000000000000
result:
ok 10 numbers
Extra Test:
score: 0
Extra Test Passed