This is a training contest on matrix exponentiation. See the tutorial along with hints and video solutions here.
Limak is always either happy or sad. His mood switches with probability $$$p$$$ every second. If Limak is happy right now, what is the probability that he's happy after $$$n$$$ seconds?
An integer $$$n$$$ ($$$1 \leq n \leq 10^9$$$) and a real value $$$p$$$ ($$$0 \lt p \lt 1$$$) with at most 9 digits after floating point.
Print one line with the answer. The absolute error allowed is $$$10^{-6}$$$.
1 0.7
0.3000000000
2 0.1
0.8200000000
11 0.06
0.6225404294
In the first sample test, there's probability $$$0.7$$$ that Limak changes his mood from happy to sad. Otherwise (with probability $$$0.3$$$), he stays happy.
In the second sample test, the answer is $$$0.1 \cdot 0.1 + 0.9 \cdot 0.9 = 0.82$$$ because we want Limak either to switch his mood twice or not to change the mood at all.
Limak can be either happy or sad. His mood changes (or stays same) when he reads an English uppercase letter. Letters S and D always make him sad, H makes him happy, and every vowel (AEIOU) flips his mood. Other letters do nothing.
Limak is happy right now. Among all $$$26^n$$$ possible strings with $$$n$$$ uppercase English letters, count such strings that Limak will be happy after reading that string. Print the answer modulo $$$10^9+7$$$.
An integer $$$n$$$ ($$$1 \leq n \leq 10^{18}$$$).
Print the answer modulo $$$1000000007$$$.
1
19
2
403
11
145418665
There are 19 strings of length $$$n = 1$$$ that will leave Limak happy: B, C, F, G, H, J, K, L, M, N, P, Q, R, T, V, W, X, Y, Z. The string "O" shouldn't be counted because the mood is switched from happy to sad.
For $$$n = 2$$$, there are 403 good strings: AA, AE, AH, AI, AO, AU, BB, ..., RZ, SA, SE, SH, SI, SO, SU, TB, TC, TF, ..., YQ, YR, YT, YV, YW, YX, YY, YZ, ZB, ZC, ZF, ZG, ZH, ZJ, ZK, ZL, ZM, ZN, ZP, ZQ, ZR, ZT, ZV, ZW, ZX, ZY, ZZ. The string "AO" is counted because the mood flips twice. Similarly, the string "SO" is counted because it first makes Limak sad (letter S) and then switches his mood from sad to happy (letter O).
Find the $$$n$$$-th Fibonacci number modulo $$$10^9+7$$$.
So, you need to find $$$F_n$$$ in the sequence defined as $$$F_0 = 0$$$, $$$F_1 = 1$$$ and $$$F_i = F_{i-1} + F_{i-2}$$$ for $$$i \geq 2$$$.
An integer $$$n$$$ ($$$0 \leq n \leq 10^{18}$$$).
Print the answer modulo $$$1000000007$$$.
3
2
6
8
50
586268941
The first few terms of Fibonacci sequence are $$$(0, 1, 1, 2, 3, 5, 8, 13, \ldots)$$$. In particular, we have $$$F_0 = 0$$$, $$$F_3 = 2$$$ and $$$F_6 = 8$$$. And for the last sample test:
$$$$$$F_{50} = 12586269025 \equiv 586268941 \pmod {10^9 + 7}$$$$$$
You are given a graph with $$$n$$$ vertices (numbered $$$1$$$ through $$$n$$$) and $$$m$$$ directed edges. Count paths consisting of $$$k$$$ steps (edges) and print the answer modulo $$$10^9+7$$$. A path can visit the same vertex or edge multiple times.
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$0 \leq m \leq n \cdot (n - 1)$$$, $$$1 \leq k \leq 10^9$$$) — the number of vertices, the number of edges and the length of a path.
The following $$$m$$$ lines describe edges. The $$$i$$$-th of these lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$), denoting a directed edge from $$$a_i$$$ to $$$b_i$$$. There are no self-loops or multiple edges.
Print the answer modulo $$$1000000007$$$.
3 4 2 1 2 2 3 3 1 2 1
5
5 10 11 2 3 4 2 2 1 2 4 1 5 5 2 3 2 3 1 3 4 1 2
21305
In the first sample test, we are given the following graph with $$$n = 3$$$ vertices and $$$m = 4$$$ edges.
There are 5 paths of length $$$k = 2$$$:
- $$$1 \rightarrow 2 \rightarrow 1$$$
- $$$1 \rightarrow 2 \rightarrow 3$$$
- $$$2 \rightarrow 1 \rightarrow 2$$$
- $$$2 \rightarrow 3 \rightarrow 1$$$
- $$$3 \rightarrow 1 \rightarrow 2$$$
A knight stands in the top-left corner of an $$$8 \times 8$$$ chessboard. You can move it at most $$$k$$$ times. Count such possible paths modulo $$$2^{32}$$$.
Formally, count paths of cells $$$(C_1, C_2, \ldots, C_s)$$$ such that $$$1 \leq s \leq k+1$$$ and a knight can move from $$$C_i$$$ to $$$C_{i+1}$$$ for every $$$i$$$.
(A chess knight moves to a square that is two squares away horizontally and one square vertically, or one away horizontally and two vertically.)
An integer $$$k$$$ ($$$0 \leq k \leq 10^9$$$).
Print the answer modulo $$$2^{32} = 4294967296$$$.
1
3
2
15
6
17231
In the first sample test, a knight can either stay in the initial cell $$$(1, 1)$$$ or move to $$$(2, 3)$$$ or $$$(3, 2)$$$. That's 3 ways in total.
You are given a graph with $$$n$$$ vertices (numbered $$$1$$$ through $$$n$$$) and $$$m$$$ directed weighted edges. Find the minimum possible total weight of a path with $$$k$$$ edges. A path can visit the same vertex or edge multiple times.
If there is no path with $$$k$$$ edges, print IMPOSSIBLE instead.
The first line contains three integers $$$n$$$, $$$m$$$ and $$$k$$$ ($$$1 \leq n \leq 100$$$, $$$0 \leq m \leq n \cdot (n - 1)$$$, $$$1 \leq k \leq 10^9$$$) — the number of vertices, the number of edges and the length of a path.
The following $$$m$$$ lines describe edges. The $$$i$$$-th of these lines contains three integers $$$a_i$$$, $$$b_i$$$ and $$$c_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$, $$$-10^9 \leq c_i \leq 10^9$$$), denoting a directed edge from $$$a_i$$$ to $$$b_i$$$ of weight $$$c_i$$$. There are no self-loops or multiple edges.
Print the minimum possible sum of weights of a path with $$$k$$$ edges, or the word IMPOSSIBLE if there is no such path.
3 4 2 1 2 12 2 3 -5 3 1 20 2 1 -1
7
3 4 5 1 2 12 2 3 -5 3 1 20 2 1 -1
17
6 5 3 1 3 -50 2 4 -51 4 3 -52 3 6 -53 4 5 -54
-156
6 5 4 1 3 -50 2 4 -51 4 3 -52 3 6 -53 4 5 -54
IMPOSSIBLE
The drawing below shows the graph in two first sample tests. The optimal paths are respectively $$$1 \rightarrow 2 \rightarrow 3$$$ and $$$2 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3$$$.
The formula for Fibonacci numbers $$$F_i = 1 \cdot F_{i-1} + 1 \cdot F_{i-2}$$$ is an example of a linear recurrence relation. Let's consider a more general and difficult formula, which additionally involves the current index $$$i$$$.
Consider an infinite sequence defined by its first $$$n$$$ elements $$$a_0, a_1, \ldots, a_{n-1}$$$ and coefficients $$$c_1, \ldots, c_n, p, q, r$$$. For every $$$i \geq n$$$:
$$$$$$a_i = \left(c_1 \cdot a_{i-1} + c_2 \cdot a_{i-2} + \dots + c_n \cdot a_{i-n}\right) + p + i \cdot q + i^2 \cdot r$$$$$$
Find the value $$$a_k \bmod 10^9+7$$$.
The first line contains two integers $$$n$$$ $$$(1 \leq n \leq 10)$$$ and $$$k$$$ $$$(1 \leq k \leq 10^{18})$$$.
The second line contains $$$n$$$ integers $$$a_0, a_1, \dots, a_{n-1}$$$ $$$(0 \leq a_i \lt 10^9+7)$$$ — the first $$$n$$$ elements of the sequence.
The third line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_{n}$$$ $$$(0 \leq c_i \lt 10^9+7)$$$.
The fourth and last line contains three integers $$$p, q, r$$$ $$$(0 \leq p, q, r \lt 10^9+7)$$$.
Print one line containing the number $$$a_k$$$ modulo $$$10^9+7$$$.
2 2 0 30 2 1 2 1 1
68
1 3 5 1 2 3 4
85
In the first sample, the sequence is defined as $$$a_0=0$$$, $$$a_1=30$$$, $$$a_i=(2a_{i-1} + a_{i-2}) + 2 + i + i^2$$$, so $$$a_k=a_2=(2 \cdot 30 + 0) + 2 + 2 + 4=68$$$.
In the second sample, the first few elements of the sequence are $$$(5, 14, 38, 85, 163)$$$. As $$$k = 3$$$, we print $$$a_3 = 85$$$.
Limak can be either happy or sad. His mood changes (or stays same) when he reads an English uppercase letter. Letters S and D always make him sad, H makes him happy, and every vowel (AEIOU) flips his mood. Other letters do nothing. Limak is happy right now and he wants to be happy after reading a string.
Let a valid character denote a question mark ? or an uppercase English letter A-Z.
You are given a pattern-string $$$s$$$ with $$$n$$$ valid characters. If there are, say, $$$x$$$ question marks, there are $$$26^x$$$ ways to replace them with uppercase letters A-Z. Your task is to count ways of replacing so that Limak would be happy after reading a new string (if he's happy before).
Additionally, there are $$$q$$$ updates of form ,,$$$i \ c$$$", each modifying one character of the pattern $$$s$$$. You need to print the answer before updates and after every update, modulo $$$10^9+7$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 200\,000$$$) — the length of the pattern and the number of updates.
The second line contains the initial pattern $$$s$$$ with $$$n$$$ valid characters.
Each of the following $$$q$$$ lines contains an integer $$$i$$$ ($$$1 \leq i \leq n$$$) and a valid character $$$c$$$. The update changes the $$$i$$$-th character of $$$s$$$ to $$$c$$$. No update tries to change a character into the same character.
Characters in $$$s$$$ are $$$1$$$-indexed. After you change a character, this change stays on (updates are not temporary).
Print $$$q+1$$$ lines, each with the current answer modulo $$$1000000007$$$.
2 5 A? 2 O 1 H 1 ? 2 ? 2 H
6 1 0 7 403 26
The pattern-string $$$s$$$ is initially A? and then after every next update: AO, HO, ?O, ??, ?H.
For the initial pattern A?, there are six good ways to replace all question marks: AA, AE, AH, AI, AO, AU. The first letter is a vowel so it flips Limak's mood from happy to sad. The second letter must be a vowel or H.
You are given a graph with $$$n$$$ vertices (numbered $$$1$$$ through $$$n$$$) and $$$m$$$ directed edges.
You need to answer $$$q$$$ queries: given $$$s, t, k$$$, count paths consisting of $$$k$$$ steps (edges) from vertex $$$s$$$ to vertex $$$t$$$, modulo $$$10^9+7$$$. A path can visit the same vertex or edge multiple times.
The first line contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \leq n, q \leq 200$$$, $$$0 \leq m \leq n \cdot (n - 1)$$$) — respectively the number of vertices, edges and queries.
The following $$$m$$$ lines describe edges. The $$$i$$$-th of these lines contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$), denoting a directed edge from $$$a_i$$$ to $$$b_i$$$. There are no self-loops or multiple edges.
The following $$$q$$$ lines describe queries. Each line contains three integers $$$s$$$, $$$t$$$ and $$$k$$$ ($$$1 \leq s, t \leq n$$$, $$$1 \leq k \leq 10^9$$$) — the start and end of a path, and its length in edges.
For each query, print a line with the answer modulo $$$1000000007$$$.
3 4 4 1 2 2 3 3 1 2 1 1 2 6 3 3 5 1 3 1 3 2 54
2 1 0 922111
In the first sample test, we are given the following graph with $$$n = 3$$$ vertices and $$$m = 4$$$ edges.
In the first query, there are 2 paths of length $$$k = 6$$$ from vertex $$$1$$$ to vertex $$$2$$$:
- $$$1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 2$$$
- $$$1 \rightarrow 2 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2$$$