The credit for us solving the problem in-contest goes to om_mittal7 who noticed that there was exactly $$$\frac{1}{2}$$$ chance that any given $$$n$$$ would have $$$(n-1,2)$$$ as a valid solution. Thereafter he tried extrapolating the idea to few more cases, and we ended up coding the following algorithm (without proof):

For $$$b_2$$$ in $$$2, 3, \cdots 1000$$$ let $$$[d_k,d_{k-1}, \cdots, d_1,d_0]_{b_2}$$$ be the base-$$$b_2$$$ representation of $$$n$$$. If there exists $$$b_1>b_2$$$ such that $$$d_k \cdot b_1+d_{k-1}=n$$$ and $$$d_k,d_{k-1}<b_1$$$, then $$$(b_1,b_2)$$$ is an answer. If nothing is found, print $$$-1$$$.

$$$1000$$$ was chosen as an arbitrarily high number that looked 'safe enough' (lol), Fortunately, the solution passed, leaving us relieved yet perplexed. However, when I tried later, I was completely stuck on how to prove its correctness.

It was only after I abandoned all previous ideas, and started from scratch with a completely new set of observations that I was able to chalk up the following proof, after which it became quite clear as to why this solution is correct. Sometimes a shift in perspective works wonders :-D

Fun fact: Brute forcing for values upto $$$10000$$$ revealed to me that $$${1,2,3,4,5,8,11,19}$$$ were the only inputs in that range for which the answer was $$$-1$$$. This suspiciously small bound turns up quite organically in the proof, which is one of the reasons why math is so beautiful (Spoiler: These are also the only inputs with answer $$$-1$$$).

/* 
 * author: twoplusthree 
 * created: 11.04.2024 20:24:53 
 */
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(),(x).end()
using vi=vector<int>;
void solve(){
  int n;
  cin>>n;
  if(n>=20){
    int b;
    int low,hig,mid;
    low=2;
    hig=1e9+5;
    while(low<=hig){
      mid=(low+hig)/2;
      if((mid+1)*mid<=n){
        b=mid;
        low=mid+1;
      }else{
        hig=mid-1;
      }
    }
    assert(2*b*b-1>=n);
    int q=n/b;
    int x=q-b; assert(1<=x&&x<=b-1);
    cout<<(n-x)<<" "<<b<<"\n";
  }else{
    auto tobase=[](int x,int b)->vi{
      vi res;
      while(x>0){
        res.push_back(x%b);
        x/=b;
      }
      reverse(all(res));
      return res;
    };
    vi bas[n];
    for(int i=2;i<n;i++){
      bas[i]=tobase(n,i);
    }
    auto isprefix=[](vi& v1,vi& v2)->bool{
      int n=(int)v1.size();
      if((int)v2.size()<n){
        return false;
      }
      for(int i=0;i<n;i++){
        if(v1[i]!=v2[i]){
          return false;
        }
      }
      return true;
    };
    for(int i=2;i<n;i++){
      for(int j=2;j<i;j++){
        if(isprefix(bas[i],bas[j])){
          cout<<i<<" "<<j<<"\n";
          return;
        }
      }
    }
    cout<<-1<<"\n";
  }
  return;
}
signed main(){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  int tt=1;
  cin>>tt;
  for(int i=1;i<=tt;i++){
    //cout<<"Case #"<<i<<": ";
    solve();
  }
  return 0;
}

Although we were unable to solve this problem in-contest, we had managed to make the pivotal claim about the case when $$$n$$$ is odd (albeit without proof).

One possible solution to the problems is where the answer for even $$$n$$$ is any Magic Square of order $$$\frac{n}{2}$$$, which can be constructed using a suitable construction algorithm (reference), which we unfortunately did not know at the time of the contest :(

However, a far simpler and arguably more elegant solution to the problem exists which was mainly inspired by the submission made by Team cns_lena_chahiye_tha (vikram108, ParadigmShift, dhruvsomani).

Clearly, $$$\max(R_i)\geq\frac{S}{r}$$$ and $$$\min(C_j)\leq\frac{S}{c}$$$ $$$\implies \max(R_i)-\min(C_j)\geq S\cdot\frac{c-r}{rc}$$$

From the problem statement, $$$S\cdot\frac{c-r}{rc} \leq \lceil\frac{n}{2}\rceil$$$

Since all the elements of $$$M$$$ are distinct, we can say $$$S\geq \displaystyle\sum_{i=0}^{rc-1}i=\frac{(rc-1)\cdot rc}{2}$$$.

Hence,

When $$$n=2m+1$$$,

$$$\frac{(2mr+r-r^2-1)(2m+1-2r)}{2} \leq m+1$$$

$$$\implies \frac{(2mr+r-r^2-1)(2m+1-2r)}{2} \leq m+1$$$

$$$\implies f(r)=2r^3-(6m+3)r^2+(4m^2+4m+3)r-(4m+3)\leq 0$$$

Studying the above function, we find that the curve first increases and then decreases in $$$0<r\leq \frac{2m+1}{2}$$$.

Putting $$$r=1$$$, we get $$$f(1)=4m^2-6m-1 >0 \ \forall m>1$$$

Putting $$$r=m$$$, we get $$$f(m)=m^2-m-3 >0 \ \forall m>2$$$

Hence, we can conclude that there does not exist any integral value of $$$r \in (0,\frac{n}{2}]$$$ such that the above condition is satisfied when $$$m>2$$$.

Let $$$(A_{i_1j_1},B_{i_1j_1})=(A_{i_2j_2},B_{i_2j_2})$$$.

Hence,

By $$$(2)-(1)$$$,

But,

/* 
 * author: twoplusthree 
 * created: 02.04.2024 01:30:38 
 */
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define all(x) (x).begin(),(x).end()
using vi=vector<int>;
void solve(){
  int n;
  cin>>n;
  if(n&1){
    if(n==3){
      cout<<"1 2\n";
      cout<<"0 1\n";
    }else if(n==5){
      cout<<"2 3\n";
      cout<<"0 3 4\n";
      cout<<"5 2 1\n";
    }else{
      cout<<-1<<"\n";
    }
  }else{
    int nn=n/2;
    vector<vi> A(nn,vi(nn));
    for(int i=0;i<nn;i++){
      for(int j=0;j<nn;j++){
        A[i][j]=(i+j)%nn;
      }
    }
    vector<vi> B(nn,vi(nn));
    for(int i=0;i<nn;i++){
      for(int j=0;j<nn;j++){
        B[i][j]=(2*i+j)%nn;
      }
    }
    vector<vi> ans(nn,vi(nn));
    for(int i=0;i<nn;i++){
      for(int j=0;j<nn;j++){
        ans[i][j]=nn*A[i][j]+B[i][j];
      }
    }
    cout<<nn<<" "<<nn<<"\n";
    for(int i=0;i<nn;i++){
      for(int j=0;j<nn;j++){
        cout<<ans[i][j]<<" ";
      }
      cout<<"\n";
    }
  }
  return;
}
signed main(){
  ios::sync_with_stdio(false);
  cout.tie(nullptr);
  int tt=1;
  cin>>tt;
  for(int i=1;i<=tt;i++){
    //cout<<"Case #"<<i<<": ";
    solve();
  }
  return 0;
}

Alice and Bob are playing a game. They start with $$$n$$$ piles of $$$1$$$ stone each. Alice always makes the first move. At any turn, a player can choose any two non-empty piles and merge them into one large pile, provided that the total number of stones in the new composite pile does not exceed $$$m$$$. If at any point, a player is unable to make a move, he/she loses the game and the opponent is declared the winner. Find out who wins the game if both Alice and Bob play optimally.

For example, let $$$n = 6$$$ and $$$m = 2$$$. The game may proceed as follows:

• Initially there are $$$6$$$ piles of $$$1$$$ stone each $$$[1, 1, 1, 1, 1, 1]$$$.
• Alice merges the $$$3^{rd}$$$ and $$$4^{th}$$$ piles to get $$$[1, 1, 2, 0, 1, 1]$$$.
• Bob merges the $$$1^{st}$$$ and $$$5^{th}$$$ piles to get $$$[2, 1, 2, 0, 0, 1]$$$.
• Alice merges the $$$6^{th}$$$ and $$$2^{nd}$$$ piles to get $$$[2, 0, 2, 0, 0, 2]$$$
• Bob cannot make any other move without making the size of the pile exceed $$$m = 2$$$, so Alice wins.

It can be proved that Alice always has a winning strategy in the above case.

Test Cases

$$$n = 6, m = 2 \implies Alice$$$
$$$n = 6, m = 3 \implies Bob$$$
$$$n = 9, m = 10 \implies Bob$$$
$$$n = 5, m = 3 \implies Alice$$$

"If $$$(n - \lceil \frac{n}{m} \rceil)$$$ is an odd integer, then Alice wins. Otherwise Bob wins."

Here $$$\lceil . \rceil$$$ is the ceiling function.

For the given test cases,
$$$(6 - \lceil \frac{6}{2} \rceil) = 6 - 3 = 3, odd \implies Alice$$$
$$$(6 - \lceil \frac{6}{3} \rceil) = 6 - 2 = 4, even \implies Bob$$$
$$$(9 - \lceil \frac{9}{10} \rceil) = 9 - 1 = 8, even \implies Bob$$$
$$$(5 - \lceil \frac{5}{3} \rceil) = 5 - 2 = 3, odd \implies Alice$$$

For a given $$$n$$$ and $$$m$$$ as defined in the problem statement, we start from the game state $$$\lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace^A$$$, where every integer in the multi-set represents the size of a non-empty pile of stones, and the superscript $$$A$$$ indicates that it is Alice's turn to move.

We call a certain game state the sink state, defined as —

In other words, the sink state is a state of the game in which at most one of the non-empty piles of stones has $$$\leq m$$$ stones, and the rest have exactly $$$m$$$ stones. It is clear that no further moves can be made from the sink state.

For example, let $$$n = 17, m = 5$$$. The sink state for this case would be $$$\lbrace 5, 5, 5, 2 \rbrace^B$$$.

Notice that the sink state is not the only possible terminal state of the game. For example, $$$\lbrace 5, 3, 3, 3, 3\rbrace^A$$$ is a terminal game state, since no further move can be made from this state.

The sink state is a terminal state, but it is not the only one.

We can see that the total number of non-empty piles in the sink state is $$$\lceil \frac{n}{m} \rceil$$$. Now, since every valid move reduces the total number of non-empty piles by exactly one, the total number of moves required to go from the start state to the sink state is $$$moves = n - \lceil \frac{n}{m} \rceil$$$.

Clearly, the winner of any game that ends in the sink state depends on the parity of $$$moves$$$. If $$$moves$$$ is odd, Alice wins. Otherwise, Bob wins.

We define the attacker to be the player (Alice or Bob) who wins the game if it ends in the sink state. The other player is the defender.

Claim:

It is always possible for the attacker to play a sequence of moves such that the game ends in the sink state, irrespective of the moves played by the defender.

Proof:

The game starts at $$$S_0 = \lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace^A$$$. If $$$n = 1$$$ or $$$m = 1$$$, then this is a trivial sink state.

Otherwise if $$$n, m > 1$$$, Alice only has one move, after which we go to $$$S_1 = \lbrace 2, \underbrace{1, 1, ...}_{(n - 2) \rm\ times} \rbrace^B$$$. If $$$n = 2$$$, then we end up at another trivial sink state.

Otherwise if $$$n > 2$$$, Bob can choose between two different moves:

• If $$$m \geq 3$$$, merge a $$$1$$$ with $$$2$$$ to go to $$$S_{21} = \lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$$$

• If $$$n \geq 4$$$, merge two $$$1$$$'s to go to $$$S_{22} = \lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^A$$$

If $$$n = 3$$$, then Bob is compelled to play the first move, which leads us to a sink state, too.

If $$$m = 2$$$, then the players are forced to play the same move of merging two $$$1$$$'s, which will end in the sink state after a finite number of moves.

So henceforth, we discuss the case where $$$n \geq 4$$$ and $$$m \geq 3$$$.

We now make the following observation —

A pile that has exactly $$$m$$$ stones is unmodifiable, irrespective of the number of stones in other piles. Hence, a state $$$\lbrace m, x_1, x_2, x_3 ...\rbrace^P$$$ is equivalent to the state $$$\lbrace x_1, x_2, x_3 ...\rbrace^P$$$.

Alice's attack strategy

On the third move, Bob can move to one of two states, as shown earlier:

• If Bob moves to $$$\lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$$$, Alice merges $$$3$$$ and $$$1$$$.

• If Bob moves to $$$\lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^A$$$, Alice merges $$$2$$$ and $$$2$$$.

Notice that both these moves bring us to the same game state $$$\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^B$$$.

Comparing this to the game state $$$S_1$$$, we find that effectively, the largest pile of stones increased by two stones, and the total number of piles decreased by two.

Using the same idea Alice can keep moving along the following sequence of game states —

Alice continues this until either —

$$$n - 2k = 0$$$, in which case we have a trivial sink state.

$$$2k = m$$$ or $$$2k + 1 = m$$$.

• When $$$2k = m$$$, we have the state $$$\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B$$$. Alice proceeds further using Bob's attack strategy, since this is like playing a new game with $$$(n - m)$$$ stones where Bob plays the first move instead of Alice.

• When $$$2k + 1 = m$$$

  • If Bob merges $$$2k$$$ with $$$1$$$, we go to the state $$$\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A$$$. Alice proceeds further using the same attack strategy since this is like playing a new game with $$$(n - m)$$$ stones.
  • If Bob merges two $$$1$$$'s to go to the state $$$\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^A$$$, Alice merges $$$2k$$$ with $$$1$$$ to get to $$$\lbrace m, 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^B \equiv \lbrace 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^B$$$. Here too, Alice proceeds using the same attack strategy, since this is equivalent to the state $$$S_1$$$ in a game with $$$(n - m)$$$ stones. Note that in the state $$$\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^A$$$, $$$(n - m - 1)$$$ cannot be zero.

Bob's attack strategy

On the third move, from state $$$S_1$$$, Bob moves to $$$S_{21} = \lbrace 3, \underbrace{1, 1, ...}_{(n - 3) \rm\ times} \rbrace^A$$$ by merging $$$2$$$ and $$$1$$$.

Next, Alice can move to one of two states:

• If Alice merges $$$3$$$ and $$$1$$$ to get to $$$\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace^B$$$, Bob merges $$$4$$$ and $$$1$$$.

• If Alice merges two $$$1$$$'s to $$$\lbrace 3, 2, \underbrace{1, 1, ...}_{(n - 5) \rm\ times} \rbrace^B$$$, Bob merges $$$3$$$ and $$$2$$$.

Notice that both these moves bring us to the same game state $$$\lbrace 5, \underbrace{1, 1, ...}_{(n - 5) \rm\ times} \rbrace^A$$$.

Comparing this to the game state $$$S_{21}$$$, we find that once again, the largest pile of stones increased by two stones, and the total number of piles decreased by two.

Using the same idea Bob can keep moving along the following sequence of game states —

Bob continues this until either —

$$$n - 2k - 1 = 0$$$, in which case we have a trivial sink state.

$$$2k + 1 = m$$$ or $$$2k + 2 = m$$$.

• When $$$2k + 1= m$$$, we have the state $$$\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^A$$$. Bob proceeds further using the same attack strategy, since this is like playing a new game with $$$(n - m)$$$ stones.

• When $$$2k + 2 = m$$$

  • If Alice merges $$$2k + 1$$$ with $$$1$$$, we go to the state $$$\lbrace m, \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B \equiv \lbrace \underbrace{1, 1, ...}_{(n - m) \rm\ times} \rbrace^B$$$. Bob proceeds further using Alice's attack strategy since this is like playing a new game with $$$(n - m)$$$ stones where Bob plays the first move instead of Alice.
  • If Alice merges two $$$1$$$'s to go to the state $$$\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace^B$$$, Bob merges $$$2k + 1$$$ with $$$1$$$ to get to $$$\lbrace m, 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^A \equiv \lbrace 2, \underbrace{1, 1, ...}_{(n - m - 2) \rm\ times} \rbrace^A$$$. Here too, Bob proceeds using Alice's attack strategy, since this is equivalent to the state $$$S_1$$$ in a game with $$$(n - m)$$$ stones where Bob plays the first move instead of Alice. Notice that again, $$$(n - m - 1)$$$ cannot be zero, using a similar strategy for proof as in the case for Alice.

This completes the proof.

First of all, let's begin by understanding what would happen if we could somehow make every pile of stones as large as possible. This would mean that at the end of the game, we would have some piles with $$$m$$$ stones, and one pile with $$$n \mod m$$$ stones. Clearly, the total number of non-empty piles would be $$$\lceil \frac{n}{m} \rceil$$$.

How many moves were made to get there? Well, notice that every move decreases the number of piles of stones by exactly one, since two piles are merged to form a bigger pile. We had $$$n$$$ piles initially. Thus the total number of moves that were made must be $$$moves = (n - \lceil \frac{n}{m} \rceil)$$$.

Since Alice starts the game and both of them play alternately, if $$$moves$$$ is odd, then Bob will be unable to make a move after Alice makes the last move, and will lose the game. So Alice wins. Similarly, if $$$moves$$$ is even, Bob wins.

Now, suppose $$$moves$$$ is odd. So Alice, understandably, wants to make each pile as big as possible, in order to win. Bob, however, does not want that. Can he do anything about it? No. Here's why.

• We start off with $$$n$$$ piles of $$$1$$$ stone each: $$$\lbrace \underbrace{1, 1, ...}_{n \rm\ times} \rbrace$$$

• Alice merges two piles of $$$1$$$ stone: $$$\lbrace 2, \underbrace{1, 1, ...}_{(n - 2) \rm\ times} \rbrace$$$

• Bob does not want to make the biggest pile bigger, so he merges two more $$$1$$$'s to make a $$$2$$$: $$$\lbrace 2, 2, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace$$$

• Alice smugly merges the $$$2$$$ with the biggest pile, and laughs in Bob's face: $$$\lbrace 4, \underbrace{1, 1, ...}_{(n - 4) \rm\ times} \rbrace$$$

Alice can keep doing this, until either —

• The largest pile has $$$m$$$ stones, in which case, she just moves on to another pile and starts making it bigger.

• The largest pile has $$$m - 1$$$ stones, in which case she cannot merge $$$2$$$ with it. In this case, the situation looks like $$$\lbrace m - 1, 2, \underbrace{1, 1, ...}_{(n - m - 1) \rm\ times} \rbrace$$$. However, here Alice herself merges $$$1$$$ with the biggest pile to complete it. Irrespective of what Bob plays next, Alice can again continue making the next pile bigger.

Hang on, how are we sure that in the last case, Alice can always merge a $$$1$$$ with the pile having $$$m - 1$$$ stones? What if, after Bob merges two $$$1$$$'s, there are no more $$$1$$$'s left! The proof of why this cannot happen is provided in a small spoiler window in the longer proof, go check it out.

Similarly, if $$$moves$$$ is even, then Bob is the one laughing, since now he can keep making the biggest pile bigger as that leads to his victory, and there is nothing Alice can do about it.

Thus, the parity of $$$moves$$$ determines the winner.

The problem statement is simple enough, you can do all tasks up to difficulty $$$k$$$ every hour, and you need to maximize the time spent. However, you do need to perform a task every hour. So it is always optimal to start with the easiest task(lowest difficulty), do all tasks of that difficulty, and gradually move up. The answer (maximum time spent) is the total number of unique difficulties present in the array.

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

void solve()
{
    int n;
    cin>>n;
    set<int> s;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        s.insert(x);
    }
    cout<<s.size()<<endl;
}

signed main(){
    FastIO;
    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}

Let’s analyze all the possible cases possible when we pick up any two indexes:

1. $$$s[i]=0$$$ & $$$s[j]=1$$$ : In this case, bitwise AND gives 0, and bitwise XOR gives 1. This basically means you can either keep the values as it is, or just swap them. So this implies that we can swap any 2 indexes with different bits.
2. $$$s[i]=1$$$ & $$$s[j]=0$$$ : Same case as above.
3. $$$s[i]=0$$$ & $$$s[j]=0$$$ : In this case, both bitwise AND and bitwise XOR gives 0. In short, this operation has no effect on the values of the two indexes.
4. $$$s[i]=1$$$ & $$$s[j]=1$$$ : In this case, bitwise AND gives 1, while bitwise XOR gives 0. So, this implies that we can basically flip a set bit (convert a ‘1’ to ‘0’) if we have at least 2 set-bits (or 2 ‘1’s).

Now the operations become simple enough, we can either swap two different bits, or we can flip a set bit if there are at least 2 set bits in the string.

We count the number of set-bits in string $$$s$$$ and $$$t$$$, let them be $$$cnt_s$$$ and $$$cnt_t$$$ respectively. If $$$cnt_s < cnt_t$$$, the answer is $$$NO$$$ as we can’t flip any unset bit using any operation, so there is no way to increase the set-bit count of $$$s$$$.

And if the count of set-bits in both strings are equal, then the answer is obviously $$$YES$$$, as we can swap any 2 different bits to get the required string.

Now, for the case when $$$cnt_s > cnt_t$$$, the answer is $$$YES$$$ (as we can always decrease the count of set-bits in $$$s$$$), except for the case when $$$cnt_t$$$ is equal to $$$0$$$, as it is not possible to make the set-bit count of $$$s$$$ equal to $$$0$$$ if there are positive number of such bits.

#include<bits/stdc++.h>
#define int long long
#define endl "\n"
#define FastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;

void solve()
{
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    int cnt=0,cntt=0;
    for(auto &it:s)
    {
        if(it=='1')
        cnt++;
    }
    for(auto &it:t)
    {
        if(it=='1')
        cntt++;
    }
    if(cnt<cntt || (cnt>0 && cntt==0))
    {
        cout<<"No"<<endl;
        return;
    }
    cout<<"Yes"<<endl;
}

signed main(){
    FastIO;
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}

Let $$$f(l)$$$ be the sum of costs of all good subarrays starting at $$$l$$$. The answer will be the sum of $$$f(l)$$$ for all $$$1 \leq l \leq n$$$.

Consider the following definitions:

• $$$g(l, r) = l + (l + 1) + (l + 2) + \ldots + r = \frac{(r + l) \cdot (r - l + 1)}{2}$$$.

• $$$next(l) =$$$ maximum position $$$r$$$ such that subarray $$$A[l \ldots r]$$$ is good.

• $$$h(l, r) = \sum_{x = l}^{r} a_x \cdot (r - x + 1). = (\sum_{x = l}^{r}a_x) \cdot (r + 1) - \sum_{x = l}^{r} x \cdot a_x$$$

We will calculate $$$f(l)$$$ using the contribution technique, i.e., the contribution of each element in our answer.

For an array $$$A$$$ of length $$$n$$$ of distinct elements, $$$A = (A_1, A_2, \ldots, A_n)$$$, observe that the contribution of element $$$i$$$ over all prefixes is given by $$$C(i) = A_i \cdot (i + (i + 1) + (i + 2) + \ldots + n) = A_i \cdot g(i, n)$$$.

Thus, for all subarrays starting at $$$l$$$, contribution $$$C(x) = A_x \cdot g(x - l + 1, \text{next}(l) - l + 1)$$$ for all $$$l \leq x \leq \text{next}(l)$$$.

Let us calculate the values of $$$f(l)$$$ from $$$l = n$$$ to $$$1$$$.

$$$f(n) = a_n$$$.

Let $$$r = next(l + 1)$$$. When we add a new element $$$a_l$$$ to the front, the contribution $$$C(x)$$$ changes from $$$a_x \cdot g(x - l, r - l)$$$ to $$$a_x \cdot g(x - l + 1, r - l + 1)$$$ as the length of the prefixes increases by $$$1$$$.

$$$\Delta C(x) = a_x \cdot (r - x + 1)$$$.

Let $$$r' = next(l)$$$.

$$$f(l) = f(l + 1) + \sum_{x = l + 1}^{r} \Delta C(x) + a_l \cdot g(1, r - l + 1) = f(l + 1) + h(l + 1, r) + a_l \cdot g(1, r - l + 1)$$$

If $$$r = r'$$$, we have correctly calculated the value of $$$f(l)$$$.

If $$$r \gt r'$$$ we have to change the contribution of the elements in the range $$$[l, r]$$$.

We have two cases,

For elements in $$$(r', r]$$$, we subtract, $$$\sum_{x = r' + 1}^{r} a_x \cdot g(x - l + 1, r - x + 1)$$$. Iterating naively works here as every element is removed from some range at most once as $$$next(i) \leq next(i + 1)$$$.

For elements in $$$[l, r']$$$, we subtract $$$(\sum_{x = l}^{r'} a_x) \cdot g(r' + 1 - l + 1, r - l + 1)$$$ in $$$\mathcal{O}(1)$$$ by prefix sums or we can maintain the sum of the currently active segment.

Calculation of $$$h(l, r)$$$ can be done in $$$\mathcal{O}(n)$$$ and $$$next(l)$$$ can be calculated using map by storing the next occurrence of each element in $$$\mathcal{O}(n \log n)$$$.

Time Complexity $$$\mathcal{O}(n \log n)$$$.

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
/*#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define INF 999999999999999999
#define pb push_back
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef pair<int, int> pii;
typedef vector<int> vi;
#define ff first
#define ss second 
#define printclock cerr<<"Time : "<<1000*(long double)clock()/(long double)CLOCKS_PER_SEC<<"ms\n";
#define ll long long
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rand(ll B) { return (unsigned ll)rng() % B;}

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const int mod = 1e9 + 7;
ll f(ll n){
    return n * (n + 1) / 2;
}
ll g(ll l, ll r){
    return ((r - l + 1) * (r + l) / 2) % mod;
}
int main() {
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    fast;
    ll _T = 1;
    
    cin >> _T;
    ll sum = 0;
    while (_T--) {
        ll n;
        cin >> n;
        sum += n;
        vector<ll> v(n);
        for(int i = 0; i < n; i++){
            cin >> v[i];
        }
        vector<ll> p = v;
        for(int i = 1; i < n; i++){
            p[i] += p[i - 1];
        }
        vector<ll> px = v;
        for(int i = 0; i < n; i++){
            px[i] = i * v[i];
        }
        for(int i = 1; i < n; i++){
            px[i] += px[i - 1]; 
        }
        auto getSum = [&](ll l, ll r){
            if(l > r) return 0LL;
            return (p[r] - p[l - 1]) * (r + 1) - (px[r] - px[l - 1]);
        };
        map<ll,ll> nxt;
        ll r = n - 1, ans = 0, tot = 0, seg_sum = 0;
        for(int l = n - 1; l >= 0; l--){
            ll npos = r;
            if(nxt.find(v[l]) != nxt.end()){
                npos = nxt[v[l]] - 1;
            }
            ans += getSum(l + 1, r) % mod;
            ans += v[l] * g(1, r - l + 1) % mod;
            seg_sum += v[l];
            ans %= mod;
            for(int j = r; j > npos; j--){
                seg_sum -= v[j];
                ans -= v[j] * g(j - l + 1, r - l + 1) % mod;
                ans %= mod;
            }
            seg_sum %= mod;
            if(npos < r){
                ans -= seg_sum * g(npos + 1 - l + 1, r - l + 1) % mod; 
                ans %= mod; 
            }
            r = min(r, npos);
            ans %= mod;
            if(ans < 0) ans += mod;
            tot += ans;
            tot %= mod;
            nxt[v[l]] = l;
        }
        cout << tot << "\n";
    }
    return 0;
}

We are required to count the number of valley subsequences of the array $$$h$$$. To do this, we can take the following approach — for every index $$$1 \leq q \leq n$$$, we count the total number of valley subequences considering $$$h_q$$$ as the smallest element of our subsequence. It is clear that the subsequence to the left of $$$h_q$$$ must be strictly decreasing, and that to the right must be strictly increasing.

Define $$$dpfd[i]$$$ as the number of subsequences starting at $$$i$$$ which are strictly increasing. The transition for $$$dpfd$$$ is then given by —

Similarly, we define $$$dpbk[i]$$$ as the number of subsequences ending at $$$i$$$ which are strictly decreasing. The transition for $$$dpbk$$$ is given by —

Both $$$dpfd$$$ and $$$dpbk$$$ can be computed naively in $$$\mathcal{O}(n^{2})$$$ time. Then the total number of valley subsequences is given by —

Time Complexity: $$$\mathcal{O}(n^2)$$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int _ = 2003;
const int MOD = 1e9 + 7;
int n, h[_];
int dpfd[_], dpbk[_];
int main() {
  int i, j;
  cin >> n;
  for (i = 1; i <= n; i++) {
    cin >> h[i];
    dpfd[i] = dpbk[i] = 0;
  }
  for (i = n; i >= 1; i--) {
    dpfd[i] = 1;
    for (j = i + 1; j <= n; j++) {
      if (h[i] < h[j]) {
        dpfd[i] = (dpfd[i] + dpfd[j]) % MOD;
      }
    }
  }
  for (i = 1; i <= n; i++) {
    dpbk[i] = 1;
    for (j = i - 1; j >= 0; j--) {
      if (h[j] > h[i]) {
        dpbk[i] = (dpbk[i] + dpbk[j]) % MOD;
      }
    }
  }
  int ans = 0;
  for (i = 1; i <= n; i++) {
    ans = (ans + (ll)dpbk[i] * dpfd[i]) % MOD;
  }
  cout << ans << "\n";
  return 0;
}

In this version of the problem, we can use the same approach as in D1, but we cannot afford to compute $$$dpfd$$$ and $$$dpbk$$$ in $$$\mathcal{O}(n^2)$$$ time. Instead, we can use a Fenwick Tree along with co-ordinate compression to optimise the time complexity down to $$$\mathcal{O}(n \cdot \log(n))$$$, which passes the constraints. Refer to this article for a detailed explanation of the underlying idea.

Time Complexity: $$$\mathcal{O}(n \cdot \log(n))$$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int _ = 100005;
const int MOD = 1e9 + 7;
int n, h[_];
int dpfd[_], dpbk[_];
struct FenwickTree {
  vector < int > bit; 
  int n;
  FenwickTree(int n) {
    this -> n = n + 1;
    bit.assign(n + 1, 0);
  }
  int sum(int idx) {
    int ret = 0;
    for (++idx; idx > 0; idx -= idx & -idx) {
      ret = (ret + bit[idx]) % MOD;
    }
    return ret;
  }
  int sum(int l, int r) {
    return (MOD + sum(r) - sum(l - 1)) % MOD;
  }
  void add(int idx, int delta) {
    for (++idx; idx < n; idx += idx & -idx) {
      bit[idx] = (bit[idx] + delta) % MOD;
    }
  }
};
int main() {
  int i, j;
  cin >> n;
  map < int , int > cmp;
  for (i = 1; i <= n; i++) {
    cin >> h[i];
    cmp[h[i]];
    dpfd[i] = dpbk[i] = 0;
  }
  int cnt = 0;
  for (auto &x : cmp) {
    x.second = ++cnt;
  }
  FenwickTree tfd(cnt + 3);
  for (i = n; i >= 1; i--) {
    dpfd[i] = (1 + tfd.sum(cmp[h[i]] + 1, cnt)) % MOD;
    tfd.add(cmp[h[i]], dpfd[i]);
  }
  FenwickTree tbk(cnt + 3);
  for (i = 1; i <= n; i++) {
    dpbk[i] = (1 + tbk.sum(cmp[h[i]] + 1, cnt)) % MOD;
    tbk.add(cmp[h[i]], dpbk[i]);
  }
  int ans = 0;
  for (i = 1; i <= n; i++) {
    ans = (ans + (ll)dpbk[i] * dpfd[i]) % MOD;
  }
  cout << ans << "\n";
  return 0;
}

When an element is pushed to the stack, observe the new size of the stack. For each value of the new stack size, store :

• at which time instants this stack size is obtained?
• what was the value added at that time instant to obtain this stack size?

In a query if we want to find out what was the $$$n^{th}$$$ stack element at the $$$t^{th}$$$ time instant, we simply binary search over the time instants stored for stack size $$$n$$$ to find out the last element added before or on time instant $$$t$$$.

#include <bits/stdc++.h>
#define fast                                                                  \
    ios_base::sync_with_stdio (false);                                        \
    cin.tie (NULL);                                                           \
    cout.tie (NULL)
 
using namespace std;

signed main() 
{
    fast;  

    int n,q;
    cin>>n>>q;

    vector <pair<int,int>> pos[n+1];
    vector <int> s(n+1);

    stack <int> st;
    for(int i=1;i<=n;i++)
    {
        string str;
        cin>>str;

        if(str=="Push")
        {
            int x;
            cin>>x;
            st.push(x);
            pos[st.size()].push_back({i,x});
        }
        else
        {
            st.pop();
        }
        s[i]=st.size();
    }

    int last=0;
    while(q--)
    {
        int i,j;
        cin>>i>>j;
        i=(i+last)%n+1;
        j=(j+last)%s[i]+1;
        int loc=s[i]-j+1;
        auto itr=lower_bound(pos[loc].begin(),pos[loc].end(),make_pair(i+1,0));
        itr--;
        last=itr->second;
        cout<<last<<"\n";
    }
    
    return 0;
}

Observe that the answer is independent of the starting positions of Alice and Bob. It depends only upon the difference ($$$b - a$$$) between their current position co-ordinates. At any move, one can decrease this difference by $$$0$$$, $$$2$$$ or $$$3$$$, constrained by their last move. If the difference becomes $$$0$$$ or negative, the game ends.

Let us consider that $$$dif$$$ is the current difference, $$$mylast$$$ is the last move played by the player whose turn it is currently and $$$hislast$$$ is the last move of their opponent. We define a boolean function $$$f(dif, mylast, hislast)$$$ which is $$$1$$$ iff the given game state is winning, otherwise it is $$$0$$$.

From the conditions given in the problem:

• $$$f(0,mylast,hislast) = 0$$$; (opponent landed on the player's spot on the previous turn)
• $$$f(dif,mylast,hislast) = 1$$$ if $$$dif < 0$$$; (opponent crossed the player's spot on the previous turn)

$$$f(dif, mylast, hislast)$$$ can be recursively defined as follows:

• If there exists any $$$move \in \lbrace 0, 2, 3 \rbrace$$$ such that $$$move \neq mylast$$$ and $$$f(dif - move, hislast, move) = 0$$$, then it is $$$1$$$, since it is always optimal to play that move.

• Otherwise, it is $$$0$$$.

Our answer for every test case is given by $$$f(b - a, -1,-1)$$$ (any invalid value may be used in place of $$$-1$$$). We can memoise $$$f$$$ to pass the time constraints. Note that $$$f$$$ is independent of the starting positions, so recomputing $$$f$$$ freshly for every test case is redundant and will get TLE verdict.

Time Complexity: $$$\mathcal{O}(N)$$$ over all test cases, where $$$N$$$ is the maximum value of $$$b - a$$$

#include <bits/stdc++.h>
using namespace std;
const int _ = 100003;
int a, b;
int dp[_][4][4];
bool ok[_][4][4];
bool f(int dif, int mylast, int hislast) {
  if (dif == 0) {
    return 0;
  } else if (dif < 0) {
    return 1;
  }
  if (ok[dif][mylast][hislast]) {
    return dp[dif][mylast][hislast];
  }
  int i;
  bool res = 0;
  for (i = 0; i <= 3; i++) {
    if (i == 1 || i == mylast) {continue;}
    res |= !f(dif - i, hislast, i);
  }
  ok[dif][mylast][hislast] = 1;
  return dp[dif][mylast][hislast] = res;
}
void solve() {
  cin >> a >> b;
  bool winning = f(b - a, 1, 1);
  cout << (winning ? "Alice" : "Bob") << "\n";
}
int main() {
  int tt;
  cin >> tt;
  memset(ok, 0, sizeof(ok));
  while (tt--) {
    solve();
  }
  return 0;
}

Let $$$a$$$ and $$$b$$$ be coprime integers such that $$$a$$$ Sickles are exactly equal in weight to $$$b$$$ Galleons. Hence, $$$a \cdot s = b \cdot g \implies \frac{a}{b} = \frac{g}{s}$$$ which indicates that $$$a$$$ and $$$b$$$ are the numerator and denominator of the reduced form of $$$\frac{g}{s}$$$.

Since the net weight of the coins must remain unchanged, we are only allowed to replace $$$ka$$$ Sickles with $$$kb$$$ Galleons, where $$$k$$$ is a whole number. If $$$17 \cdot b > a$$$, it is optimal to replace as many Sickles as possible, for which $$$k = \lfloor \frac{n}{a} \rfloor$$$. Otherwise the answer is $$$n$$$.

Time Complexity: $$$\mathcal{O}(\log(\min(s, g)))$$$ per test case

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int s, g, n;
void solve() {
  cin >> s >> g >> n;
  int x = gcd(s, g);
  int a = g / x;
  int b = s / x;
  int k = n / a;
  ll ans = max((ll)n, (ll)k * b * 17 + n % a);
  cout << ans << "\n";
}
int main() {
  int tt;
  cin >> tt;
  while (tt--) {
    solve();
  }
  return 0;
}

Let us consider that the capacity of Upayan's bag is $$$b$$$ books. Let $$$[x_0, x_1, ... x_{n - 1}]$$$ be the order in which we choose to return the books (first we return the book at index $$$x_0$$$, then $$$x_1$$$, and so on). Hence, the total fine imposed is —

Claim 1: It is always optimal to return the books sorted in the order of descending $$$p_i$$$.

Claim 2: $$$F$$$ decreases monotonically with $$$b$$$.

Thus, we can use Binary Search to find the minimum value of $$$b$$$ ($$$1 \leq b \leq n$$$), for which $$$F(x, b) \leq r$$$. If there exists no such $$$b$$$, the answer is $$$-1$$$.

Time Complexity: $$$\mathcal{O}(n \cdot \log(n))$$$

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int _ = 1000003;
int n, l[_], p[_], lsum;
ll r;
bool ok(int k) {
  int i;
  ll pot = lsum;
  for (i = 0; i < n; i++) {
    pot += p[i] * (i / k + 1);
  }
  return (pot <= r);
}
int main() {
  int i;
  cin >> n >> r;
  lsum = 0;
  for (i = 0; i < n; i++) {
    cin >> l[i];
    lsum += l[i];
  }
  for (i = 0; i < n; i++) {
    cin >> p[i];
  }
  sort(p, p + n, [](int x, int y) {
    return (x > y);
  });
  int ans = -1;
  int lo, hi, mid;
  lo = 1;
  hi = n;
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (ok(mid)) {
      ans = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }
  cout << ans << "\n";
  return 0;
}

A quick observation reduces this problem to trivial if-else cases. A queen never takes more than 2 moves to get from any point on the chessboard to any other point on the board (as it can always move vertically to get to the Rth row in the first move, and then horizontally to reach the Cth column in the second move). Thus, it can reach (R, C) in a maximum of two moves.

The answer is zero iff the queen is already at (R, C). The queen needs one move iff (R, C) lies on the same diagonal, vertical or horizontal as itself. In all other cases, 2 moves are needed.

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

void solve()
{
    int n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    if (x1 == x2 && y1 == y2)
        cout<<"0\n";
    else if ((x1 == x2) || (y1 == y2) || (abs(x2 - x1) == abs(y2 - y1)))
        cout<<"1\n";
    else
        cout<<"2\n";
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    cin >> t;
    for (int i = 1; i <= t; i++)
        solve();
    return 0;
}

TLE Elimination Step: Since it was asked to find total pairs staisfying $$$(arr[j]-arr[i])^2$$$ == $$$(j-i)$$$ Notice that LHS is always perfect square no. so for the inequality to hold,RHS must also be a perfect sqaure no. So,its just sufficient to check only over pairs when $$$(j-i)$$$ is a perfect square no. so for every index '$$$i$$$' keeping it fixed we only iterate over of all indexes of form $$$i+1,i+4,i+9,i+16......i+j*j<n$$$ and check for the condition.

#include <bits/stdc++.h>

using namespace std;
#define int long long
#define FastIO ios_base::sync_with_stdio(false);
cin.tie(NULL);

signed main() {
    FastIO;
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
      cin >> arr[i];
    }
    int count = 0;
    for (int i = 0; i < n; i++) {
      int j = 1;
      while (i + j * j < n) {
        if ((arr[i + j * j] - arr[i]) * (arr[i + j * j] - arr[i]) == (j * j)) {
          count++;
        }
        j++;
      }
    }
    cout << count;
    return 0; 
}

We use a min-heap priority queue to store the zombies' health in ascending order.Also we keep a note of summation of heath of zombies and the total damage so far.The use of the priority queue allows for efficient removal of zombies with health less than or equal to the total damage so far.

For event type 1,we increment the total damage by $$$x$$$ and pops out zombies whose health was <= total damage so far and decrementing its health from total sum.

For event type 2, we simply push the new zombie's health considering its health as (y+total damage so far) and also increment its new health in total sum.

For event type 3,the remaining sum of all alive zombies is calculated by subtracting the damage multiplied by the number of remaining zombies(size of the priority queue) from the total sum and thereby printing the result.

#include <bits/stdc++.h>

using namespace std;
#define int long long
const int N = 1e5 + 1;

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, q;
    cin >> n >> q;
    int t;
    long long sum = 0;
    priority_queue < int, vector < int > , greater < int >> pq;
    for (int i = 0; i < n; i++) {
      cin >> t;
      sum += t;
      pq.push(t);
    }
    int damage = 0;
    while (q--) {
      cin >> t;

      if (t == 1) {
        int x;
        cin >> x;
        damage += x;
        while (pq.size() && pq.top() <= damage) {
          sum -= pq.top();
          pq.pop();
        }
        if (t == 2) {
          int y;
          cin >> y;
          sum += (damage + y);
          pq.push(damage + y);
        }
        if (t == 3) {
          int res = sum - damage * pq.size();
          cout << res << '\n';
        }
      }
    }
    return 0;
}

Observe that there are only $$$p = 15$$$ primes till $$$50$$$. Therefore, every number can be represented by a $$$p$$$-bit bitmask where the $$$i^{th}$$$ bit is $$$1$$$ if the power of the $$$i^{th}$$$ prime is odd in the number. The mask of the product of two numbers is simply the $$$\oplus$$$ (bitwise XOR) of the their masks and a perfect square has mask $$$0$$$. Henceforth, $$$A_v$$$ will be used to refer to the mask of node $$$v$$$.

We root the tree arbitrarily and define $$$dp[v][m]$$$ as the number of subgraphs which contain $$$v$$$ as the highest node in the rooted tree and have mask $$$m$$$. Then, the answer is $$$\sum_{v = 1}^{n} dp[v][0]$$$. In order to calculate $$$dp[v]$$$, let's define $$$dp_i[v][m]$$$ as the number of subtrees containing $$$v$$$ itself and $$$0$$$ or more nodes from the subtrees of the first $$$i$$$ children of $$$v$$$ so that the nodes form a connected subgraph and their XOR is $$$m$$$. $$$dp_0[v][m]$$$ is $$$1$$$ for $$$m = A_v$$$ and $$$0$$$ otherwise. Then, $$$dp_i[v][m]$$$ can be calculated as

where $$$c_i$$$ is the $$$i^{th}$$$ child of $$$v$$$ and $$$M = 2^p - 1$$$ is the maximum possible mask.

This has complexity $$$O(n \cdot 2^{2p})$$$ which is too slow. But, it can be seen that the transition from $$$dp_{i - 1}[v]$$$ to $$$dp_{i}[v]$$$ is simply a XOR convolution of $$$dp_{i - 1}[v]$$$ and $$$dp[c_i]$$$ and can be calculated with FWHT in $$$O(p \cdot 2^p)$$$ time to speed up the solution to $$$O(n \cdot p \cdot 2^p)$$$ which is fast enough.

#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define END "\n"
#define rall(v) (v).rbegin(), (v).rend()
#define all(v) (v).begin(), (v).end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define rep(i, from, to) for (int i = from; i < (to); ++i)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;

const ll mod = 998244353; // change to something else

ll euclid(ll a, ll b, ll &x, ll &y) {
	if (!b) return x = 1, y = 0, a;
	ll d = euclid(b, a % b, y, x);
	return y -= a/b * x, d;
}

struct Mod {
	ll x;
	Mod(ll xx = 0) : x(xx) {}
	Mod operator+(Mod b) { return Mod((x + b.x) % mod); }
	Mod operator-(Mod b) { return Mod((x - b.x + mod) % mod); }
	Mod operator*(Mod b) { return Mod((x * b.x) % mod); }
	Mod operator/(Mod b) { return *this * invert(b); }
	Mod invert(Mod a) {
		ll x, y, g = euclid(a.x, mod, x, y);
		assert(g == 1); return Mod((x + mod) % mod);
	}
	Mod operator^(ll e) {
		if (!e) return Mod(1);
		Mod r = *this ^ (e / 2); r = r * r;
		return e&1 ? *this * r : r;
	}
};

typedef vector<Mod> vi;

void FST(vi& a, bool inv) {
	for (int n = sz(a), step = 1; step < n; step *= 2) {
		for (int i = 0; i < n; i += 2 * step) rep(j,i,i+step) {
			Mod &u = a[j], &v = a[j + step]; tie(u, v) =
				// inv ? pii(v - u, u) : pii(v, u + v); // AND
				// inv ? pii(v, u - v) : pii(u + v, u); // OR /// include-line
				pair<Mod, Mod>(u + v, u - v);                   // XOR /// include-line
		}
	}
	if (inv) for (Mod& x : a) x = x / sz(a); // XOR only /// include-line
}
vi conv(vi a, vi b) {
	FST(a, 0); FST(b, 0);
	rep(i,0,sz(a)) a[i] = a[i] * b[i];
	FST(a, 1); return a;
}

vector<int> primes;
const int maxN = 50;

void do_primes() {
    for (int i = 2; i <= maxN; ++i) {
        bool ok = true;
        for (int j = 2; j * j <= i; ++j) {
            if (i % j == 0) {
                ok = false;
                break;
            }
        }
        if (ok) primes.push_back(i);
    }
}

int prime_mask(int a) {
    int mask = 0;
    for (int i = 0; i < primes.size(); ++i) {
        while (a % primes[i] == 0) mask ^= (1 << i), a /= primes[i];
    }
    return mask;
}

void solve(){
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
        A[i] = prime_mask(A[i]);
    }
    const int L = 1 << primes.size();
    vector<vi> dp(n, vi(L, 0));
    Mod ans = 0;
    auto dfs = [&] (auto&& self, int v, int p) -> void {
        dp[v][A[v]].x = 1;
        for (auto u: adj[v]) {
            if (u != p) {
                self(self, u, v);
                dp[v] = conv(dp[v], dp[u]);
            }
        }
        ans = ans + dp[v][0];
        dp[v][0] = dp[v][0] + 1;
    };
    dfs(dfs, 0, -1);
    cout << ans.x << '\n';
}
int main()
{
    do_primes();
    fastio
    int t = 1;
    // cin>> t;
    while(t--) solve();
    return 0;
}