Soluție HackerRank pentru Down the Rabbit Hole, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Down the Rabbit Hole
- Domeniu: Number Theory
- Limbaj: C++14
Challenge: Down the Rabbit Hole
Subdomeniu: Number Theory (number-theory)
Scor cont: 120.0 / 120
Submission status: Accepted
Submission score: 1.0
Submission ID: 464775647
Limbaj: cpp14
Link challenge: https://www.hackerrank.com/challenges/down-the-rabbit-hole/problem
Cerință
Alice is feeling bored while sitting on the riverbank with her sister, when she notices a 2D White Rabbit with a 2D pocket watch run past. She follows it down a rabbit hole when suddenly she falls a long way to a curious 2D plane.
In this 2D plane she discovered she can only move using a sequence of *movements*. Those movements are limited to:
- Scaling, denoted as S_c (where c is a nonzero rational number). If Alice is currently at (x,y), then S_c takes her to (cx,cy).
- Translation, denoted as T_a,b (where a and b are rational numbers). If Alice is currently at (x,y), then T_a,b takes her to (a+x,b+y).
- Rotation, denoted as R_a,b (where a and b are rational numbers and a^2 + b^2 = 1). If Alice is currently at (x,y), then R_a,b takes her to (ax+by,ay-bx). In other words, R_a,b is a clockwise rotation about the origin, at an angle theta where cos theta = a and sin theta = b.
- Flip X-axis, denoted as F_X. If Alice is currently at (x,y), then F_X takes her to (x,-y).
- Flip Y-axis, denoted as F_Y. If Alice is currently at (x,y), then F_Y takes her to (-x,y).
- Inversion, denoted as I (more precisely, inversion in the unit circle). If Alice is currently at (x,y), then I takes her to displaystyle ≤ft((x / x^2+y^2), (y / x^2+y^2)right).
Also, Alice discovered that when she is at (0,0) before she performs an inversion, she is taken to a special place called *Wonderland*. In Wonderland, performing any of the other movements (scaling, translation, rotation or flip) will return her to Wonderland, and performing an inversion moves her back to (0,0).
Now, Alice has a sequence of N such movements to make. Moreover, she performs this sequence of N movements a total of K times. Your task is to determine her final location after her adventure.
If Alice's final location is (x_f,y_f), it's easy to see that x_f and y_f are rational. Let x_f = A/B and y_f = C/D (both in lowest terms). Understandably, A, B, C and D can be really large integers, so instead of asking for x_f and y_f we will only ask for the values AB^-1 bmod (10^9+7) and CD^-1 bmod (10^9+7).
Input Format
The first input contains a single integer, T, which is the number of test cases. The next lines contain the descriptions of the T test cases.
The first line of each test case contains four values N, K, x_s and y_s. N and K are integers (described above), and (x_s,y_s) is the initial location of Alice (x_s and y_s are rational numbers).
The next N lines each contains the description of a movement in the sequence, which is one of the following:
- `S c`, which denotes *scaling* (c is a nonzero rational number),
- `T a b`, which denotes *translation* (a and b are rational numbers),
- `R a b`, which denotes *rotation* (a and b are rational numbers and a^2 + b^2 = 1),
- `F X`, which denotes *flip X-axis*,
- `F Y`, which denotes *flip Y-axis*, and
- `I`, which denotes *inversion*.
Output Format
If Alice's final location is Wonderland, output `WONDERLAND`.
If Alice's final location is (x_f,y_f), and x_f = A/B and y_f = C/D in irreducible form, then output the two integers AB^-1 bmod (10^9+7) and CD^-1 bmod (10^9+7) in a line separated by a single space. However, if either B or D is not invertible, also output `WONDERLAND`.
Constraints
1 ≤ T ≤ 10^5
1 ≤ N ≤ 10^5
The sum of the N's in a single test file is ≤ 10^5
1 ≤ K ≤ 10^15
Each rational number is expressed in irreducible form A/B with the following constraints:
-10^9 < A < 10^9
1 ≤ B < 10^9
Sample Input
2
3 2 0/1 0/1
T -2/1 3/1
R 3/5 4/5
I
5 1 2/1 -2/1
F X
S 3/2
T -3/1 -3/1
I
F Y
Sample Output
881896558 492241383
WONDERLAND
Explanation
In the first test case, (x_s, y_s) = (0, 0), K = 2 and the sequence of operations is [T_-2,3, R_3/5, 4/5, I].
begin{array}{rccc}
text{T_-2,3:} & (0, 0) & rightarrow & (-2, 3)
text{R_3/5,4/5:} & (-2, 3) & rightarrow & (6/5, 17/5)
text{I:} & (6/5, 17/5) & rightarrow & (6/65, 17/65)
text{T_-2,3:} & (6/65, 17/65) & rightarrow & (-124/65, 212/65)
text{R_3/5,4/5:} & (-124/65, 212/65) & rightarrow & (476/325, 1132/325)
text{I:} & (476/325, 1132/325) & rightarrow & (119/1160, 283/1160)
end{array}
Therefore, the final location is (x_f, y_f) = (119/1160, 283/1160). So we print:
119· 1160^-1 bmod (10^9+7) = 881896558 and:
283· 1160^-1 bmod (10^9+7) = 492241383.
In the second test case, (x_s, y_s) = (2, -2), K = 1 and the sequence of operations is [F_X, S_3/2, T_-3,-3, I, F_Y].
begin{array}{rccc}
text{F_X:} & (2, -2) & rightarrow & (2, 2)
text{S_3/2:} & (2, 2) & rightarrow & (3, 3)
text{T_-3,-3:} & (3, 3) & rightarrow & (0, 0)
text{I:} & (0, 0) & rightarrow & text{Wonderland}
text{F_Y:} & text{Wonderland} & rightarrow & text{Wonderland}
end{array}
Therefore, the final location is *Wonderland*.
Cod sursă
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<vii> vvll;
const int mod = 1000000007;
int w[] = {0, 1, 4, 5};
int u[] = {2, 3, 6, 7};
ll mpow (ll x, ll n){
ll res = 1;
while(n){
if(n & 1)
res = res * x % mod;
n /= 2;
x = x * x % mod;
}
return res;
}
ll inv(ll x){
return mpow(x, mod - 2);
}
vvl id(int k){
vvl v(k, vl(k));
for(int i = 0; i < k; ++i)
v[i][i] = 1;
return v;
}
vvl mul(const vvl &x, const vvl &y){
int n = x.size();
vvl res(n, vl(n));
for(int i = 0; i < 4; ++i) for(int j = 0; j < 4; j += 1){
for(int l = 0; l < 4; ++l){
res[w[i]][w[j]] += x[w[i]][w[l]]*y[w[l]][w[j]];
res[u[i]][u[j]] += x[u[i]][u[l]]*y[u[l]][u[j]];
}
res[w[i]][w[j]] %= mod;
res[u[i]][u[j]] %= mod;
}
return res;
}
vvl mulfast(const vvl &x, const vvl &y){
int n = x.size();
vvl res(n, vl(n));
for(int i = 0; i < 4; ++i){
for(int j = 0; j < 4; j += 2){
for(int l = 0; l < 4; ++l){
res[w[i]][w[j]] += x[w[i]][w[l]] * y[w[l]][w[j]];
}
res[w[i]][w[j]] %= mod;
}
}
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; j += 2){
res[u[i]][u[j]] = res[w[i]][w[j]];
}
for(int i = 1; i < 4; i += 2)
for(int j = 1; j < 4; j += 2){
res[w[i]][w[j]] = res[w[i - 1]][w[j - 1]];
res[u[i]][u[j]] = res[u[i - 1]][u[j - 1]];
}
for(int i = 0; i < 4; i += 2)
for(int j = 1; j < 4; j += 2){
res[w[i]][w[j]] = -res[w[i + 1]][w[j - 1]];
res[u[i]][u[j]] = -res[u[i + 1]][u[j - 1]];
}
return res;
}
ll in(){
ll x, y;
scanf("%lld/%lld", &x, &y);
return x * inv(y) % mod;
}
void out(const vl & v){
for(int i = 0; i < v.size(); ++i)
cerr << v[i] << ' ';
cerr << endl;
}
void out(const vvl & v){
cerr << endl;
for(int i = 0; i < v.size(); ++i)
out(v[i]);
}
void eval(ll x, ll y, const vvl & a){
vl t(8);
for(int i = 0; i < 8; ++i)
t[i] = (a[i][0]+a[i][6]) % mod;
ll xz = (t[6] + t[4] * x - t[5] * y) % mod;
ll yz = (t[7] + t[4] * y + t[5] * x) % mod;
if(xz == 0 && yz == 0){
printf("WONDERLAND\n");
} else{
ll xn = (t[2] + t[0] * x - t[1] * y) % mod;
ll yn = (t[3] + t[0] * y + t[1] * x) % mod;
ll d = (xz * xz + yz * yz) % mod;
assert(d);
ll di = inv(d);
ll xf = ((xz * xn + yz * yn) % mod * di % mod + mod) % mod;
ll yf = ((-yz * xn + xz * yn) % mod * di % mod + mod) % mod;
printf("%lld %lld\n", xf, yf);
}
}
pii mul(pii x, pii y){
return pii((x.first * y.first - x.second * y.second) % mod, (y.first * x.second + y.second * x.first) % mod);
}
void mul(pii & z, pii x, pii y){
z.first = (z.first + x.first * y.first - x.second * y.second) % mod;
z.second = (z.second + y.first * x.second + y.second * x.first) % mod;
}
pii mpow(pii x, ll n){
pii res(1, 0);
while(n){
if(n & 1) res = mul(res, x);
x = mul(x, x);
n /= 2;
}
return res;
}
vvll mul(vvll x, vvll y){
int n = x.size();
vvll res(n, vii(n));
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
for(int l = 0; l < n; ++l)
mul(res[i][j], x[i][l], y[l][j]);
return res;
}
vvl mpow(vvl x, ll n){
vvll res(2, vii(2));
res[0][0] = res[1][1] = pii(1, 0);
vvll y(2, vii(2));
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j)
y[i][j] = pii(x[i * 4][j * 4], x[i * 4][j * 4 + 1]);
while(n){
if(n & 1) res = mul(res, y);
y = mul(y, y);
n /= 2;
}
vvl resout(8, vl(8));
for(int i = 0; i < 2; ++i)
for(int j = 0; j < 2; ++j){
resout[i * 4][j * 4] = res[i][j].first;
resout[i * 4 + 1][j * 4 + 1] = res[i][j].first;
resout[i * 4][j * 4 + 1] = res[i][j].second;
resout[i * 4 + 1][j * 4] = -res[i][j].second;
}
for(int i = 0; i < 4; ++i)
for(int j = 0; j < 4; j++){
resout[u[i]][u[j]] = resout[w[i]][w[j]];
}
return resout;
}
int main(){
int T; cin >> T;
for(int test = 1; test <= T; ++test){
ll n, k, x, y;
scanf("%lld%lld", &n, &k);
x = in();
y = in();
int cntc = 0;
vvl a = id(8);
char type;
ll a1, b, c;
for(int i = 0; i < n; ++i){
scanf("\n%c", &type);
if(type == 'I'){
cntc = 1 - cntc;
vvl x(8, vl(8));
for(int i = 0; i < 4; i += 2)
x[i][i + 4] = x[i + 4][i] = 1;
for(int i = 1; i < 4; i += 2)
x[i][i + 4] = x[i + 4][i] = -1;
a = mul(x, a);
} else if(type == 'F'){
cntc = 1 - cntc;
char ax;
scanf(" %c", &ax);
vvl x = id(8);
for(int i = 0; i < 4; ++i)
x[2 * i][2 * i] = -1;
if(ax == 'Y'){
for(int i = 0; i < 4; ++i)
x[i][i] *= -1;
}
a = mul(x, a);
} else if(type == 'S'){
c = in();
vvl x = id(8);
for(int i = 0; i < 4; ++i)
x[i][i] = c;
a = mul(x, a);
} else if(type == 'R'){
a1 = in();
b = in();
vvl x = id(8);
for(int i = 0; i < 4; i += 2){
x[i][i] = a1; x[i][i + 1] = b;
x[i + 1][i] = -b; x[i + 1][i + 1] = a1;
}
a = mul(x, a);
} else if(type == 'T'){
a1 = in();
b = in();
vvl x = id(8);
for(int i = 0; i < 4; i += 2){
x[i][i + 4] = a1; x[i][i + 5] = -b;
x[i + 1][i + 4] = b; x[i + 1][i + 5] = a1;
}
a = mul(x, a);
} else{
cerr << i << ' ' << type << endl;
assert(0);
}
}
if(n == 1){
if(type == 'F' || type == 'I'){
k %= 2;
} else if(type == 'S'){
a = id(8);
for(int i = 0; i < 4; ++i)
a[i][i] = mpow(c, k);
k = 1;
} else if(type == 'T'){
x = (x + k % mod * a1) % mod;
y = (y + k % mod * b) % mod;
k = 0;
} else if(type == 'R'){
pii t(a1, -b);
t = mpow(t, k);
a1 = t.first; b = -t.second;
a = id(8);
for(int i = 0; i < 4; i += 2){
a[i][i] = a1; a[i][i + 1] = b;
a[i + 1][i] = -b; a[i + 1][i + 1] = a1;
}
k = 1;
}
}
vvl a0 = a;
a = mul(a, a);
a = mpow(a, k / 2);
if(k % 2) a = mul(a, a0);
if(k % 2 && cntc){
y *= -1;
}
eval(x, y, a);
}
return 0;
}