For any triplet of integers $$$(b,e,m)$$$ where $$$0\le b \lt m$$$ and $$$m$$$ is prime, there exists exactly one $$$r$$$ where $$$0\le r \lt m$$$ such that
$$$$$$b^e\equiv r\pmod m$$$$$$
Dream fixed $$$b$$$ and $$$m$$$ ($$$m$$$ prime) and generated $$$n$$$ values of $$$e$$$ along with the $$$n$$$ corresponding solutions for $$$r$$$. As such, Dream now has $$$n$$$ pairs $$$(e,m)$$$. Dream also has $$$q$$$ values of $$$e$$$, respectively stored as $$$a_1,a_2,\dots,a_q$$$, that he wishes to calculate the corresponding $$$r$$$ for.
Unfortunately, Dream completely forgot the value of $$$m$$$. Given the $$$b$$$, the $$$n$$$ pairs of $$$(e,r)$$$, and the $$$q$$$ values $$$a_1,a_2,\dots,a_q$$$, please calculate $$$b^{a_i}\bmod m$$$.
The first line contains thee integers $$$b$$$, $$$n$$$, and $$$q$$$ ($$$2\le b\le 3$$$, $$$n=10^5$$$, $$$1\le q\le 100$$$).
Each of the next $$$n$$$ lines contain two integers $$$e$$$ and $$$r$$$ ($$$2\le e\le 10^9$$$).
Each of the following $$$q$$$ lines contain one integer $$$a_i$$$ ($$$2\le a_i\le 10^9$$$).
The test data guarantees that all $$$e$$$ are pairwise distinct and that exactly one $$$m$$$ can be determined by the given $$$e$$$ and $$$r$$$.
The test data further guarantees that all $$$e$$$ are randomly sampled between $$$2$$$ and $$$10^9$$$ under the condition that all $$$e$$$ are pairwise distinct.
Output $$$q$$$ lines, each line containing one integer, corresponding to the value of $$$r$$$ such that $$$0\le r \lt m$$$ and $$$b^{a_i}\equiv r\pmod m$$$.
- In the first subtask, worth $$$5$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^3$$$.
- In the second subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^9$$$.
- In the third subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^{19}$$$.
- In the fourth subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^{29}$$$.
- In the fifth subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^{99}$$$.
- In the sixth subtask, worth $$$19$$$ points, the value of $$$m$$$ satisfies $$$m\le 10^{199}$$$.
3 8 3 108 75 616 36 220 16 37 66 114 64 514 24 1919 65 810 33 19260817 123456789 23333333
3 79 49
It can be determined that $$$97$$$ is the only prime that satisfies the given conditions.
This sample does not correspond to any testcase in the actual test data.
Note that CPython may be faster than PyPy.
After the debacle of Dream's previous redstone computer, Dream has now laid the job of programming the computer to you.
The memory of Dream's redstone computer can be visualized as an array of $$$5\cdot 2^{17}$$$ integers, labeled $$$0,1,2,\dots,5\cdot 2^{17}-1$$$ respectively. Initially, the value of all positions in this array is $$$0$$$.
We will refer to the memory with label $$$x$$$ as memory $$$x$$$.
Define a Dream program as a program that runs on Dream's redstone computer. A Dream program is designed such that the result of the $$$x$$$-th instruction is stored in memory $$$x$$$, where $$$x$$$ starts from $$$0$$$. This means that the maximal instruction count of a valid Dream program is $$$5\cdot2^{17}$$$.
A Dream program can be represented as a sequence of instructions. These instructions can be one of the following:
- >: read an integer from the input of the computer. Result is this read value.
- < $$$x$$$: output the integer at memory $$$x$$$. Result is this outputted value.
- S $$$c$$$: Result is the value $$$c$$$, where $$$0\le c \lt 998244353$$$.
- + $$$x$$$ $$$y$$$: Result is the sum of memory $$$x$$$ and memory $$$y$$$.
- - $$$x$$$ $$$y$$$: Result is the difference of memory $$$x$$$ and memory $$$y$$$.
- * $$$x$$$ $$$y$$$: Result is the product of memory $$$x$$$ and memory $$$y$$$.
All arithmetic operations are done modulo $$$998244353$$$.
Now, Dream asks you to implement the Dream Dynamic Discrete Fourier Transform on an array $$$a_0,a_1,\dots,a_{n-1}$$$ in a Dream program. Specifically, the Dream program shall execute $$$q$$$ of these operations:
- 1 $$$i$$$ $$$x$$$: Multiply $$$a_i$$$ by $$$x$$$.
- 2 $$$k$$$: Define $$$x=63912897^k$$$. Output the value $$$$$$\left(\sum_{i=0}^{n-1}a_ix^i\right)\bmod 998244353$$$$$$
Note that you are not given this array! This array (in order of increasing indices) will be the input of the Dream program. You are instead asked to output a Dream program. The Dream program that you output should have output equal to the sequential answers for queries of type $$$2$$$ when given any array as input. For more details, refer to the input.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\le n,q\le2^{12}$$$).
Each of the following $$$q$$$ lines contain a description of a query, either of the form 1 $$$i$$$ $$$x$$$ ($$$0\le i \lt n$$$, $$$0\le x \lt 998244353$$$) or 2 $$$k$$$ ($$$0\le k \lt 998244353$$$).
Following this will be some data intended for the checker.
In the first line, output an integer $$$L$$$, the length of your constructed Dream program. This integer should satisfy $$$0\le L\le 5\cdot2^{17}$$$.
In the following $$$L$$$ lines, describe your Dream program, with a description of one instruction per line.
- In the first subtask, worth $$$11$$$ points, $$$n,q\le2^8$$$.
- In the second subtask, worth $$$19$$$ points, all queries are after all modifications.
- In the third subtask, worth $$$23$$$ points, $$$n,q\le2^{10}$$$.
- In the fourth subtask, worth $$$47$$$ points, no additional constraints are imposed.
3 3 2 0 1 1 108616 2 114514 5 3 1 2 3 2 6 347675984 3 249562194 77997864 782218748 2 111534453 645770907 3 427868729 963824933 961269789 2 356474745 375144741 3 716807646 177923670 143374138 2 39861101 981112147 3 541186351 838003166 750524701 2 133225512 814133617
15 > > > + 0 1 + 3 2 < 4 S 108616 S 716372446 * 1 6 * 8 7 * 7 7 * 2 10 + 0 9 + 12 11 < 13
The following fact may or may not be useful:
$$$$$$63912897\equiv3^{\frac{998244352}{2^{12}}}\pmod{998244353}$$$$$$
In the first sample, when the input of the Dream program is [1,2,3], the output is [6,347675984], which is correct.
There is an unordered multiset $$$P$$$ of lattice points on the Cartesian plane. Initially, this multiset is empty. There are $$$N$$$ modifications, where we either add or remove a point from $$$P$$$.
Any three elements of $$$P$$$ define a triangle, possibly degenerate. After each modification, Dream wonders: what is the sum of the eighth powers of the area of the triangle that any three elements selected from $$$P$$$ without replacement define?
In other words, after each modification, calculate $$$$$$\sum_{\{A,B,C\}\subset P}S_{\triangle ABC}$$$$$$ where $$$\{A,B,C\}$$$ is a subset of $$$S$$$ of size $$$3$$$. In particular, if there are less than $$$3$$$ elements of $$$P$$$, the answer is $$$0$$$.
These subsets are unordered.
Output all answers modulo $$$998244353$$$.
Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.
The first line contains a single integer $$$N$$$ ($$$1\le N\le 10^5$$$).
Each of the next $$$N$$$ lines contains three integers $$$t$$$, $$$x$$$, and $$$y$$$ ($$$0\le x,y \lt 998244353$$$), where $$$t$$$ is either $$$1$$$ or $$$2$$$. If $$$t=1$$$, the point $$$(x,y)$$$ is added to $$$P$$$; otherwise, the point $$$(x,y)$$$ is removed from $$$P$$$.
If $$$t=2$$$, then the test data guarantees that $$$(x,y)$$$ occurs at least once in $$$P$$$. Only one occurrence of $$$(x,y)$$$ is to be removed from $$$P$$$.
Output $$$N$$$ lines, each containing a single integer, equal to the requested value after the corresponding modification (modulo $$$998244353$$$.)
- In the zeroth subtask, worth $$$0$$$ points, the tests are the samples shown above.
- In the first subtask, worth $$$10$$$ points, $$$N\le 10$$$.
- In the second subtask, worth $$$20$$$ points, $$$N\le 10^3$$$.
- In the third subtask, worth $$$10$$$ points, $$$t=1$$$.
- In the fourth subtask, worth $$$60$$$ points, no additional restrictions are imposed.
7 1 0 0 1 0 1 1 2 0 2 2 0 1 4 0 2 4 0 1 6 0
0 0 1 0 256 0 6561
5 1 0 0 1 0 1 1 1 0 1 1 1 2 0 1
0 0 994344961 982646785 994344961
source: https://youtu.be/tylNqtyj0gs
I have gone over the scenarios in my head,
and there are 6.96969 billion outcomes, and only one of them -
- do I win.
Dream abstracts the fabric of spacetime as a directed rooted tree (arborescence) with $$$N$$$ nodes (numbered $$$1$$$ through $$$N$$$). Node $$$1$$$ is the root and for each $$$i$$$ ($$$1 \le i \le N-1$$$), the parent of node $$$i+1$$$ is $$$f_i$$$. All edges of this tree are directed away from the root.
Then, Dream employs a magical superpower and adds $$$M$$$ directed edges to this tree in such a way that the resulting directed graph remains acyclic (a DAG).
Let's call a node of this DAG an event and further call a simple path on this DAG an era. Dream considers a pair of events $$$(i,j)$$$ to be plausible if there is an era whose first event is $$$i$$$ and last event is $$$j$$$. Note that $$$i \lt j$$$ does not have to hold for a plausible pair.
Dream now wants you to answer $$$Q$$$ queries. In each query, he gives you two positive integers $$$l$$$ and $$$r$$$, where $$$l \leq r$$$, and he wishes to know the number of plausible pairs of events $$$(i,j)$$$ such that $$$l \leq i,j \leq r$$$.
The first line of the input contains two integers $$$N$$$ and $$$M$$$ ($$$2\le N\le 10^5$$$, $$$0\le M\le 10^5$$$).
The second line contains $$$N-1$$$ integers $$$f_1, f_2, \ldots, f_{N-1}$$$, the $$$i$$$-th of which is the father of node $$$i+1$$$. Note that $$$f_i \lt i+1$$$ does not necessarily hold!
$$$M$$$ lines follow. Each of these lines contains two integers $$$u$$$ and $$$v$$$, describing an additional edge from node $$$u$$$ to node $$$v$$$.
The following line contains a single integer $$$Q$$$ ($$$1\le Q\le 10^6$$$).
$$$Q$$$ lines follow. Each of these lines contains two integers $$$l$$$ and $$$r$$$ ($$$l\le r$$$), describing a query.
For each query, print a single line containing one integer — the number of plausible pairs $$$(i,j)$$$ such that $$$l \leq i,j \leq r$$$.
- In the zeroth subtask, worth $$$0$$$ points, the tests are the samples shown above.
- In the first subtask, worth $$$1$$$ point, the tree forms a line; that is, there exists a permutation that describes a simple path on this tree.
- In the second subtask, worth $$$11$$$ points, $$$n,q,m\le1000$$$.
- In the third subtask, worth $$$7$$$ points, $$$m\le 5$$$.
- In the fourth subtask, worth $$$23$$$ points, $$$n,q,m\le5\times10^4$$$.
- In the fifth subtask, worth $$$17$$$ poitns, $$$q\le 10^5$$$.
- In the sixth subtask, worth $$$41$$$ points, no additional restrictions are imposed.
2 2 1 1 2 1 2 1 1 2
3
8 2 1 2 5 1 4 3 3 2 4 4 7 3 4 6 5 7 1 8
6 5 27
In the first sample, the plausible pairs are $$$(1,1)$$$, $$$(1,2)$$$, and $$$(2,2)$$$.
In the second sample, the plausible pairs that contribute to the second query are $$$(5,5)$$$, $$$(5,6)$$$, $$$(5,7)$$$, $$$(6,6)$$$, and $$$(6,7)$$$.