Tournoi de Xiangqi


Submit solution

Points: 30 (partial)
Time limit: 1.0s
Python 3 3.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
C++, Java, Python

Quand Ya Xi rentre en Chine, la première chose qu'elle fait quand elle rencontre ses copines est d'organiser une partie de Xiangqi (jeu aux échecs chinois).

Le jeu se joue sur un tableau carré de dimensions \(n \times n\), dont les cases sont numérotées de \(1\) à \(n^{2}\). Le premier joueur pose \(k\) pions cylindriques superposés sur une case, le deuxième pose \(2 \times k^{2}\) pions superposés sur une autre case, le troisième \(3 \times k^{3}\) et ainsi de suite jusqu'à ce que toutes les cases soient remplies.

Etant donné la dimensions du tableau et le nombre \(k\), on aimerait savoir combien de pions il faudra pour organiser une partie de Xiangqi.

Input Specification

La première ligne du fichier d'entrée contient un entier T, le nombre de cas de tests (\(1 \le T \le 10\)).

Chacune des lignes qui vont suivre vont contenir deux entiers \(n\), \(k\) (\(1 \le n \le 10^5\) , \(1 \le k \le 10^9\)) qui donnent respectivement la dimensions du tableau et le nombre de pions posés sur la première case.

Output Specification

Pour chaque cas de test afficher le nombre de pions nécessaires pour organiser la partie de Xiangqi qui correspond. Afficher cet entier modulo \(1000000007\).

Scoring

  • \(1 \leq n \leq 6\) and \(1 \leq k \leq 10^3\) (20 points).
  • \(1 \leq n \leq 10^5\) and \( k = 1 \) (40 points).
  • \(1 \leq n \leq 10^3\) and \(1 \leq k \leq 10^9\) (40 points).

Sample Input

2
2 2
1 50

Sample Output

98
50

Comments


  • 1
    Mouad_Ouj  commented on Oct. 23, 2020, 8:17 p.m. edited

    But when we have a lot of calcul example x+y*(a-b)/n i don't know how to print it modulo

    Thank you for your help sir moncef and aymanrs


    • 2
      aymanrs  commented on Oct. 24, 2020, 7:51 p.m. edit 5

      since you're dividing you gotta use modular inverse which is discussed in the video I linked in my comment. Here's my snippet for the modular inverse: https://ideone.com/0dsmsq

      if you use it be sure to #include <tuple>. let M = 1e9 + 7. your expression modulo M is:

      {x + (long long)[y%M] [(a-b) % M] [modinv(n, M) % M]} % M

      I used {} and [] but of course you're gonna use () in your code. since the expression can be very long and hard to debug you can store parts of the expression in variables then assemble them in the end:

      //////////////////////

      int t1 = y % M;

      int t2 = ((a-b) % M + M) % M;

      int t3 = (long long)t1 * t2 % M;

      int t4 = modinv(n, M);

      int answer = (x + (long long)t3 * t4) % M;

      //////////////////////

      The additionnal stuff in the t2 line is to prevent modulos from being negative, once again it is discussed in the video I linked in my comment.

      I hope this helps :D


      • 0
        Mouad_Ouj  commented on Oct. 27, 2020, 10:21 a.m.

        thanks for help dear aymanrs


  • 1
    diaatest  commented on Oct. 22, 2020, 9:51 p.m.

    question sample test


  • 0
    Mouad_Ouj  commented on Oct. 21, 2020, 6:44 p.m.

    I don't know when using modulo 1e9+7