DCP-502: Simple Graph Back to All Problems

Medium Math > Counting


There are **2*N** nodes in a graph aligned in **2** rows , each row having **N** nodes. The nodes of the first row are sequentially numbered from **1** to **N**. The nodes of the second row are sequentially numbered from **N + 1** to **2*N**. Each node is connected to the node to its left , right , up and down. ![enter image description here][1] The distance between any two adjacent node is **1**. **D(i , j)** denotes the shortest path value between node **i** and node **j**. **Ans** is represented as the following ![enter image description here][2] You have to compute the value of **Ans** or simply all pair shortest path sum. The answer can be huge, so print it modulo **10<sup>9</sup>+7** Input: ------ Input starts with an integer **T (1<= 10<sup>5</sup>)**, denoting the number of test cases. Each case contains an integer **N (1 ≤ N ≤ 10<sup>18</sup> )**. Output: ------- Print the answer for each test case in a single line. Sample Input ------------ 3 1 2 3 Sample Output ------------- 2 16 50 [1]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/9ca38e05-c24c-cfc5-e4a6-08d57eacd894_11a6861cc12b4a729b3a4a474da2adfb_W412xH414.png [2]: https://s3-ap-southeast-1.amazonaws.com/devskillimagestorage/questionimages/6d72ac7e-5542-ca65-34ce-08d57f2a3d4f_4a419e5fc708427182ccb2c5bed96747_W369xH149.png


Problem Setter:

Fahim Shahriar Shakkhor

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 1.00
C++ 1.00
C++14 1.00
C# 2.00
Go 2.00
Java 2.00
JavaScript 2.00
Objective-C 2.00
Perl 2.00
PHP 2.00
Python 2.00
Python3 2.00
Ruby 2.00
VB.Net 2.00

Problem Stats

35/77

Solve/Submission

Ranking

# User Language Timing
01 radoslav11 Cpp 0.04s
02 KerimK Cpp 0.04s
03 CLown1331 Cpp14 0.04s
04 Zeronfinity Cpp 0.04s
05 Ahb_arif Cpp14 0.04s
06 by_default C 0.04s
07 feodorv C 0.04s
08 prateepm Cpp14 0.06s
09 mahbubcseju Cpp 0.07s
10 tanu_1603070 Cpp 0.07s
11 Hasinur_ Cpp 0.10s
12 mamun4122 Cpp14 0.12s
13 kzvd4729 Cpp14 0.13s
14 shaft Cpp14 0.17s
15 BohdanPastuschak Cpp14 0.17s
16 Superstorm Cpp14 0.18s
17 Informatimukas Cpp 0.18s
18 Pure_Protea Cpp14 0.19s
19 dipta007 Cpp 0.23s
20 shahed95 Cpp 0.25s
21 ksohan Cpp 0.25s
22 cjoa Python 0.30s
23 Trumen Cpp 0.38s
24 Masum_ice Cpp 0.40s
25 tariqiitju Python3 0.79s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support