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
Cerinta
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 \left(\frac{x}{x^2+y^2}, \frac{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 \le T \le 10^5$
$1 \le N \le 10^5$
The sum of the $N$'s in a single test file is $\le 10^5$
$1 \le K \le 10^{15}$
Each rational number is expressed in irreducible form $A/B$ with the following constraints:
$-10^9 < A < 10^9$
$1 \le 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\cdot 1160^{-1} \bmod (10^9+7) = 881896558$ and:
$283\cdot 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 sursa
#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;
}
HackerRank Number Theory – Down the Rabbit Hole