#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    cout<<n*n<<endl;
}

What is the maximum possible value of $$$d(M)$$$.

We can see that for $$$ M \le 10^18$$$, the maximum possible value of $$$d(M)$$$ is only $$$ 9 * 18$$$ attained for $$$999999999999999999$$$. So for finding the number of solutions for a given $$$N$$$, we can iterate over all the values of $$$d(M)$$$ upto $$$9 *18$$$, and then check if $$$d(N/p) == p$$$.

Try solving the easier version of the problem where we only need to find the number of distinct simple paths in DAG.

In this problem, we need to find the number of distinct simple paths in DAG, which start at a vertex with indegree 0 and end on a node with out-degree 0. To solve this problem, we first do topo-sort on the graph to get the ordering, then initialize a dp value of 0 for all nodes. For the nodes with outdegree 0, set the value of dp to 1. Then while iterating over all nodes $$$u$$$, in their topological order, update the dp value with the sum of dp value of all $$$v$$$ such that there exists an edge $$$(u,v)$$$ in the graph. In the end, print the sum of dp value of all nodes with indegree 0.

Solve the problem when $$$ M = 0$$$.

Build a graph with $$$K$$$ vertex, labelled from $$$0, 1, 2, ..., K -1 $$$. For each $$$i$$$ in range $$${1..P}$$$, add an edge from $$$j$$$ to $$$j + i$$$ for all j in range $$${0..K-1}$$$. Count the number of paths from $$$0$$$ to $$$0$$$ of length $$$N$$$.

First, we will try to solve the problem for the case where $$$M=0$$$. For doing this, build a graph with $$$K$$$ vertex, labelled from $$$0, 1, 2, ..., K -1 $$$. For each $$$i$$$ in range $$${1..P}$$$, add an edge from $$$j$$$ to $$$j + i$$$ for all j in range $$${0..K-1}$$$. Count the number of paths from $$$0$$$ to $$$0$$$ of length $$$N$$$. To do this we can define

The transition can we simply be obtained by looking at the graph, which says that

To optimize this for large N, we can see that the transitions are independent of $$$i$$$ hence we can use matrix exponentiation to find the answer

For solving the problem when $$$M!=0$$$, first find the solution that assumes there is no constraint, then we will subtract the number of solution which do not contains any of these $$$M$$$ numbers, after subtracting these two answers we will get the required value. For computing the case which contains only these $$$M$$$ numbers, we will build the graph and thus the matrix with transition using only these M values.

Try calculating the number of ways to have happiness $$$\geq i$$$.

Note that the happiness cannot exceed $$$m$$$ so we will use it as the upper bound in all summations below.

Let $$$G_i$$$ denote the number of ways to have happiness $$$\geq i$$$. One way to guarantee that we have at least $$$i$$$ happiness is to choose $$$i$$$ colours and their $$$k*i$$$ places, and fill all remaining places randomly with the non-chosen $$$m - i$$$ colours. The number of ways to do so is:

Unfortunately, this is wrong and it overcounts. Specifically, for $$$j \geq i$$$, $$$G_i$$$ counts each way with happiness $$$j$$$, $$$\binom{j}{i}$$$ times. (Try to see why?).

If we let $$$E_i$$$ denote the way to get happiness exactly $$$i$$$, this leads us to the following relation between the "incorrect" values of $$$G_i$$$ and $$$E_i$$$.

Using the above relation and induction, we can show that:

Therefore,

This expression can now be evaluated for all $$$i$$$ using FFT with coefficients as the terms in the two brackets in the final summation.

Simplify the problem first by finding the sum of edge weights from 1 to each node. Then replace socket cost by socket cost — sum of edge weight from 1. and switch cost by switch cost + sum of edge weight from 1.

If we make the reduction as shown above the problem reduces to a matching problem, when given some nodes, we have to find the matching with the maximum sum of nodes, such that a node can be paired only with nodes in its subtree.

#include<bits/stdc++.h>
using namespace std;

signed main() { int g, s, a, b; cin >> g >> s >> a >> b;

cout << ((g * a >= s * b) ? "Gold" : "Silver");
return 0;

}

Since $$$i^{th}$$$ and $$${i+k/2}^{th}$$$ character must be same, and also first half of string is equal to last half of string, this implies that the answer is "1" if and only if count of $$$1s$$$ is divisible by 4.

#include<bits/stdc++.h>
using namespace std;

signed main() {
	int t;
	cin >> t;
	for(int i=0; i<t; i++) {
		int n;
		cin >> n;
		string s;
		cin >> s;
		int cnt = 0;
		for(int j=0; j<n; j++) {
			if(s[j] == '1') cnt++;
		}
		if(cnt % 4 == 0) cout << 1 << "\n";
		else cout << 0 << "\n";
	}
	return 0;
}

If we change an element, what will be the gcd for the rest of the array?

Suppose we want to replace $$$a_i$$$ by some number $$$x$$$. The GCD of the array in this case will be $$$gcd(a_1, a_2, ... a_{i-1}, x, a_{i+1}, ... a_n)$$$. Looking at this formula, we can see that we should pre-calculate the prefix GCDs and suffix GCDs for the array as such:

Now, the GCD of the array in the above case will be $$$gcd(pre_{i-1}, x, suf_{i+1})$$$. So what should be the optimal choice of $$$x$$$ to maximize this value? Clearly, the GCD will be some divisor of $$$gcd(pre_{i-1}, suf_{i+1})$$$. It will be thus be optimal to choose $$$x$$$ as the largest divisor of $$$gcd(pre_{i-1}, suf_{i+1})$$$ smaller than or equal to $$$r$$$. Thus, we should also pre-calculate the largest divisor of each number from 1 to $$$10^5$$$ smaller than or equal to $$$r$$$, as follows:

for (int i = r; i > 0; i--)
  for (int j = i; j <= N; j += i)
    if (!largest_divisor[j]) largest_divisor[j] = i;

It is now easy to see that the answer will be the maximum of largest_divisor[__gcd(pre[i-1], suf[i+1])] over all valid $$$i$$$, as well as the GCD of the whole array itself (where no operations are done).

Let’s root the tree at any node x and find a dfs traversal. During any traversal, we can find the current path with one end point as x and the other end point as the current point dynamically while iterating over the tree in dfs.

So as we can find all paths this way. We can also push all these paths in a trie dynamically while doing dfs.

Now this problem has been transformed into a very simple problem where given any trie which was already built. In a query, answer the number of paths in the trie lexicographically smaller than the given query, which can be easily found just by iterating over the trie in O(path_length_in_query).

So instead of rooting again after every query, building trie and iterating over the trie. This can be precomputed by trying to root at every vertex one by one and finding answer for all possible paths.

So, if have rooted at any node x. Then, find answers for all the paths in a single run on the trie just by doing a single traversal like dfs.

After all this, we can answer any query in $$$O(1)$$$ using precomputed answer.

Complexity Analysis: $$$O(N*time(trie_build+trie_iterate))$$$

time(trie_build) = $$$O(N*26)$$$ — This is the worst case theoretically for trie, but it will not get achieved mostly as there can be atmost 26 direct children and for any node and all the strings are made from just adding a single new character in some old path.

time(trie_iterate) — $$$O( N )$$$

Overall complexity will be less than $$$O((N^2)*26)$$$.

The Code of testers and setters both ran in approximately 1.5 sec without any big optimizations.

Will be added soon.

First solve the case where A = B.

Add a new black vertex and connect it with both grey vertex.

Break the chain at different positions to get different trees.

Using the absolute value of the difference between the prefix sums of subtree size.

First lets solve the case where there is only one black node initially. Root the tree at this node. Denote by Dp[v], the number of ways to colour the nodes in the subtree of v, given that v is coloured black currently, We can see that it becomes

where U is a child of v. After some manipulations we can see that

To solve the original problem, where we have got two black nodes, lets add a new node and add a edge from it to both the grey nodes. So we have got a connected graph with one cycle. If we consider this new node to have the colour black, we can see that the problem is reduced to the case where we had only on grey node, but instead of tree, we now have got a graph. Lets consider all the nodes on this cycle, when we are doing these operations at some instance exactly one of these nodes would be coloured grey and all others on the cycle would be black. Lets call this node to be the node $$$v_{i}$$$, Since this node would have got the grey colours from two differen side, what we can do is to remove on the edges on it in the cycle, and the solve the problem on the tree. So our problem can be solved the following way.

1. Initialize $$$Ans = 0$$$.
2. For each edge in cycle, delete it, compute the possible ways for this new tree, and add this to ans.

Since each way has been counted twice, so we need to divide $$$Ans$$$ by 2.

Lets now see how we can implement the above process.

We know that the answer for a tree is just

, and after deletion of edges, the nodes which are not on the cycle still have the same subtree size, so we can just precompute that part.

So our count becomes

, where size[k] is the size of the kth node on the cycle after deleting some edge.

To to this first just cut one of the edge connecting the newly added node to the black nodes, and compute the subtree sizes for all nodes on the cycle for this tree.

Now define

, which is the prefix sum of the sizes of the first $i$ nodes on the cycle, we can see that if we cut the $$$i^{th}$$$ edge, the denominator becomes

.

To compute this we can first ignore the abs size and then since pref is monotonically increasing the sign can be simply achieved by finding the count of negative terms in the product. So we need to compute

for all $$$i$$$.

If we replace $$$Pref[i]$$$ by $$$x$$$ we can see that we get the following polynomial, which needs to be evaluated at $$$k$$$ points.

for all $$$i$$$.

This is equal to

evaluated at Pref[i] for all $$$i$$$.

This problem can be solved by multipoint evaluation.

If neither of $$$A$$$ or $$$B$$$ equals to zero, print $$$0$$$. Otherwise if neither of them equal $$$1$$$ then print $$$1$$$, else if neither of them equal $$$2$$$, print $$$2$$$.

If all the entries of the array are zero, then the answer is $$$0$$$.

Otherwise, if the xor of all the elements in the array is zero, then the answer is $$$1$$$. (We can select the entire array in the move).

Finally, in all other cases the answer is $$$2$$$. This is because we can select the entire array in the first move, and then again select the entire array in the second move.

The first observation is that the moves along $$$x$$$ and $$$y$$$ axis are independent of each other. So we can solve for each direction independently and then directly multiply number of ways for each direction. This will give us total number of ways for the whole grid.

So the simplified problem is how to solve for a single direction. We are given $$$N$$$ adjacent circular positions and we have to find the number of possible jump sizes so that we can reach from $$$x_1$$$ to $$$x_2$$$ using any number of moves (possibly zero). Thus,

where $$$a$$$ and $$$b$$$ are some integers. So, the above equation is satisfied when $$$x_2-x_1 \text{ mod } \gcd(\text{jump_size},N) \equiv 0$$$.

We know that the GCD of $$$N$$$ with any integer will be a divisor of $$$N$$$. So, we will iterate over all the divisors of $$$N$$$ and pre-calculate how many of them have that divisor as GCD and if that divisor is dividing $$$x_2-x_1$$$, then we can add their contribution to the answer. Hence, this way we can calculate number of ways for single direction for all the queries. To find the complete answer multiply answer of each direction and output for each query.

Time complexity: $$$O(Q(\text{div}(N)+\text{div}(M))$$$, where $$$\text{div}(x)$$$ denotes number of divisors of $$$x$$$.

First, lets build up some observations. For the following discussion, take any possible way which starts from $$$(1,1)$$$ and returns to $$$(1,1)$$$ visiting all cells exactly once.

If at some step, we move from $$$(i,j)$$$ to $$$(i+1, j)$$$, then clearly, we must have moved from $$$(i-1,j+1)$$$ to $$$(i, j+1)$$$, as there are only two ways of reaching $$$(i,j+1)$$$, either from $$$(i,j)$$$ or from $$$(i-1, j +1)$$$, but we have already moved from $$$(i,j)$$$ to $$$(i + 1,j)$$$. Building up on this, we can see that if $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ are two different cells such that $$$x_1 + y_1$$$ is equal to $$$x_2 + y_2$$$, then the move taken from $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ are equal.

Let's use $$$A(x,y)$$$ to denote the move taken from $$$(x,y)$$$. Building up on the above discussion we can see that since this the graph is actually a toroid, the point above $$$(1,a)$$$ is equivalent to $$$(H, a)$$$, and similarly continuing $$$A(1,a)$$$ and $$$A(H, a+1)$$$ are also the same. So, the total freedom in moves is heavily restricted.

The total number of distinct diagonals on the toroid are only $$$d = \gcd(H,W)$$$. So, if we fix the first $$$d$$$ moves, then all the remaining moves are automatically decided. But we cannot take any arbitrary moves for the first $$$d$$$ moves, as not all such solutions will visit all the cells. To solve this, we can fix the cells we will be reaching after the first $$$d$$$ moves. Lets say we reach the cell $$$(x, y)$$$ where $$$x+y = d + 2$$$. Now the number of steps required to reach back to $$$(1,1)$$$ from $$$(1,1)$$$, assuming the first $$$d$$$ moves takes us to $$$(x,y)$$$ is $$$\text{lcm}(\frac{H}{\gcd(H, x-1)}, \frac{W}{\gcd(W, y-1)})$$$. If this is equal to $$$\frac{HW}{d}$$$, then this solution will visit all the cells and thus be counted in the solution. So, the final answer is summation of $$$\binom{d}{x-1}$$$ over all these valid $$$(x,y)$$$.

Time complexity: $$$O(\gcd(H, W)\log(\gcd(H,W)))$$$.

Take the input in variable $$$n$$$. So if $$$n == 1$$$, print $$$AC$$$, else print $$$WA$$$.

Think of a greedy solution.

Sort the triplets if ascending order of Bi’s..

.Firstly we take a array of size 2000. This array represents the integers that are used in the sequence (represent this array as T). Now we sort the triplets in ascending order of Bi’s. We now iterate over this sorted triplets. For each triplet we find the number of elements in the interval [Ai, Bi] of the sequence by iterating over T. If this count is more than Ci, then we proceed to the next triplet. Otherwise, we need to take more elements in the sequence. We chose these new elements greedily ie. we chose the largest element available. We take new elements until the count is equal to Ci. Then we proceed to the next triplet. (Time Complexity: 2000*N + N logN)

How long can a segment be until its lcm becomes too large?

We can observe that for a fixed $$$a$$$, $$$\text{lcm}(a, a+1, a+2, ... b)$$$ will increase very rapidly as $$$b$$$ increases. In particular, for any $$$a$$$, we can show that $$$\text{lcm}(a, a+1, a+2, ... a+43) < 10^{16}$$$. This is because the product of all primes upto $$$43$$$ is already greater than $$$10^{16}$$$, and for each prime upto $$$43$$$ we know that there is at least one element in $$$[a, a+43]$$$ divisible by that prime implying that the lcm is divisible by that prime as well.

Further, note that for any $$$a$$$, $$$\text{lcm}(a, a+1, a+2) \geq \frac{a(a+1)(a+2)}{2}$$$. Thus, we also have that for $$$b \geq 3\cdot 10^5$$$, $$$\text{lcm}(b-2, b-1, b) \geq 10^{16}$$$. So for all segments with lengths $$$\geq 3$$$, the right endpoint must be smaller than $$$3\cdot 10^5$$$, and for each such endpoint we only need to go through a handful of segments with that endpoint. Thus, we have the following solution:

1. Iterate through the right endpoints $$$r$$$ from $$$2$$$ to $$$3\cdot 10^5$$$. For each such number, start iterating through the left endpoints $$$l$$$ backwards from $$$r - 1$$$ until $$$\text{lcm}(l, ... r - 1, r)$$$ exceeds $$$10^{16}$$$ (be careful of overflows).

2. Maintain a global map, counting for each lcm its frequency. This is the map that we will update as we iterate through the segments as explained above. Now, once we are done with a particular endpoint $$$r$$$, we can answer each query with bounds equal to $$$r$$$ there.

3. We are now left to answer queries with $$$r > 3\cdot 10^5$$$. Clearly, the answer for such a query is the value stored in the map after we are done iterating, along with possibly some number of segments of length $$$2$$$ with that lcm. Thus, we now only need to find out for which $$$a$$$, is $$$\text{lcm}(a, a+1) = x$$$. As $$$\text{lcm}(a, a+1) = a(a+1)$$$, we only need to solve a quadratic equation to find the value of $$$a$$$. If the value of $$$a$$$ is an integer and smaller than $$$r$$$, we can add $$$1$$$ to the value in map. Thus, all queries have been answered in sufficient time.