PROFESSOR MORIARITY Solutions BVPCSI06

PROFESSOR MORIARITY Solutions BVPCSI06

A total twofold tree exists with n hubs and all the edges in this tree are undirected. Hubs are numbered from 1ton. Consider the root hub with the index1, and the parent of ith hub as floor (I/2). 

Moriarity sees this tree and needs to make intricacies. He adds m extra undirected edges to the tree. Sherlock is delegated to check the quantity of Beautiful Paths in the subsequent diagram modulo 109+7. 

A Beautiful Path is an exchanging succession of nearby hubs and undirected edges, which starts and finishes with hubs and doesn’t contain any hub more than once. Do take note of that a solitary hub is additionally viewed as a legitimate Beautiful way under this definition. It would be ideal if you allude to the models and notes underneath for occasions. 

Info The main line of information contains two space-isolated numbers n and m — the quantity of hubs in the tree and the quantity of additional edges individually. 

The accompanying m lines each contains two space-isolated numbers u and v — portraying an undirected additional edge whose endpoints are u and v. 

Note that there might be different edges between hubs in the subsequent diagram. 

Yield Yield one number — the quantity of excellent ways in the subsequent chart, modulo 109 + 7. 

 

Imperatives 

(1 ≤ n ≤ 109,0 ≤ m ≤ 4) 

(1 ≤ u, v ≤ n,u ≠ v) 

 

Test input 

3 0 

 

Test Output 

 

Test input 

3 1 

2 3 

 

Test Output 

15

 

Test input 

2 4 

1 2 

2 1 

1 2 

2 1 

 

Test Output 

12 

 

Clarifications: 

In the primary model the ways are: (1);(2);(3);(1, 2);(2, 1);(1, 3);(3, 1);(2, 1, 3);(3, 1, 2). (For clearness, the edges between hubs are precluded since there are no numerous edges for this situation.) 

In the subsequent model, the ways are: (1);(1, 2);(1, 2, 3);(1, 3);(1, 3, 2); and likewise for ways beginning with 2and3. (5 × 3 = 15 ways altogether.) 

 

In the third model, the ways are: (1);(2); any undirected edge associating the two hubs went in either bearing. (2 + 5 × 2 = 12 ways altogether.)

Solution

 
CODE C++14 :
 

 

 
#include<bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int mod=1000000007;
map<int,int>sz;
set<int>vis;
map<int,vector<int> >g;
int n,m,ans;
 
int get_sz(int t){
 int ret=0;
 for(int i=0;(t<<i)<=n;++i)
  ret+=min(((t+1)<<i),n+1)-(t<<i);
 return ret;
}
void ins_node(int x){for(;x;x/=2)sz[x]=0;}
 
void dfs(int x,int y){
 vis.insert(x);
 ans=(ans+(ll)y*sz[x])%mod;
 for(int i:g[x])if(!vis.count(i))dfs(i,y);
 vis.erase(x);
}
 
int main(){
 ins_node(1);
 for(cin>>n>>m;m –> 0;){
  int x,y;cin>>x>>y;
  g[x].push_back(y);g[y].push_back(x);
  ins_node(x);ins_node(y);
 }
 for(auto i:sz){
  int u=i.first,v=u/2;
  int res=get_sz(u);sz[u]+=res;
  if(v){sz[v]-=res;g[u].push_back(v);g[v].push_back(u);}
 }
 for(auto i:sz)dfs(i.first,i.second);
 cout<<ans<<‘n’;
 return 0;
}

 

 

 

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

1. Frog Sort Solution Codechef

2. Chef and Meetings Solution Codechef

3. Maximise Function Solution Codechef

4. Highest Divisor Solution Codechef

5. Cut the Cake Challenge Solution Codechef

6. Dream and the Multiverse Solution Codechef

7. Cell Shell Solution Codechef

8. Multiple Games Solution Codechef

9. Another Tree with Number Theory Solution Codechef

10. XOR Sums Solution Codechef

11. Prime Game Solution CodeChef

12. Team Name Solution Codechef

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :

Leave a Comment