We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #15: Lattice paths
  4. Discussions

Project Euler #15: Lattice paths

Sort by

recency

|

120 Discussions

|

  • CS_2212256_T
     + 0 comments
    import java.util.Scanner;

public class Solution {
    public static long factorial(int n) {
        long result = 1;
        for (int i = 1; i <= n; i++) {
            result = (result * i) % (1000000007);
        }
        return result;
    }

    public static long pow(long base, long exponent, long mod) {
        long result = 1;
        base = base % mod;
        while (exponent > 0) {
            if (exponent % 2 == 1) {
                result = (result * base) % mod;
            }
            exponent = exponent / 2;
            base = (base * base) % mod;
        }
        return result;
    }

    public static long modInverse(long a, long m) {
        return pow(a, m - 2, m);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        scanner.nextLine(); // Consume newline left-over
        for (int i = 0; i < t; i++) {
            String[] item = scanner.nextLine().split(" ");
            int n = Integer.parseInt(item[0]);
            int m = Integer.parseInt(item[1]);
            long answer = (factorial(n + m) * modInverse((factorial(n) * factorial(m)) % 1000000007, 1000000007)) % 1000000007;
            System.out.println(answer);
        }
    }
}

  • blackspring
     + 0 comments
    #python
import math
for i in range(int(input())):
    n, m=map(int, input().split())
    print(math.comb(n+m, m) %(10**9+7))

  • SAGILE_MANOJ_KU1
     + 0 comments

    for C#

    using System;

    class Program { const int MOD = 1000000007;

    static int CountRoutes(int N, int M)
{
    int[,] dp = new int[N + 1, M + 1];

    for (int i = 0; i <= N; i++)
    {
        for (int j = 0; j <= M; j++)
        {
            if (i == 0 || j == 0)
            {
                dp[i, j] = 1;
            }
            else
            {
                dp[i, j] = (dp[i - 1, j] + dp[i, j - 1]) % MOD;
            }
        }
    }

    return dp[N, M];
}

static void Main()
{
    int T = int.Parse(Console.ReadLine());

    for (int t = 0; t < T; t++)
    {
        string[] input = Console.ReadLine().Split();
        int N = int.Parse(input[0]);
        int M = int.Parse(input[1]);

        int result = CountRoutes(N, M);
        Console.WriteLine(result);
    }
}

    }

  • srikv
     + 0 comments

    passed all test cases

    # Enter your code here. Read input from STDIN. Print output to STDOUT
import sys

sys.setrecursionlimit(5000)

def findpath(n , m, seen):
    if (n,m) in seen:
        return(seen[(n,m)]%(7+10**9))
    if n == 0 or m == 0:
        return(1)
    else:
        seen[(n,m)] = (findpath(n-1,m,seen)+findpath(n,m-1,seen))%(7+10**9)
        return(seen[(n,m)])
        
seen = {(0,0): 1}

findpath(500, 500, seen)

for a0 in range(int(input())):
    n, m =list(map(int, input().split()))
    print(seen[(n, m)])

    for a0 in range(int(input())): n, m =list(map(int, input().split())) print(seen[(n, m)])****

  • prasanthsai1526
     + 0 comments

    My Solution in Java given below:- import java.util.; import java.math.; public class Solution {

    public static void main(String[] args) 
{
    Scanner sc = new Scanner(System.in);
    int T=sc.nextInt();
    for(int i =0;i<T;i++)
    {
        int N=sc.nextInt();
        int M=sc.nextInt();

    BigInteger path = fact(BigInteger.valueOf(N+M)) .divide(fact(BigInteger.valueOf(N))) .divide(fact(BigInteger.valueOf(M))) .mod((BigInteger.valueOf(1000000007))); System.out.println(path.toString());

        }
    sc.close();
}

    static BigInteger fact(BigInteger num) { if (num == BigInteger.ZERO) return BigInteger.ONE;

        return num.multiply(fact(num.subtract(BigInteger.ONE )));
}

    }