q1a2z3 Just thinking through the problem, I realized it's just a sideways Pascal's Triangle. Let's say our word is "ABCDE".
- A B C
- B C D
- C D E
Let's look at each individual spot and how many paths there are to them. The "C" in the top right and bottom left have only one path to them, and the same can be said of the "B"s and "A". So, we can write the grid like:
- 1 1 1
- 1 C D
- 1 D E
Now, looking at the remaining "C", there are two ways to reach it. You can either come in from above, or come in from the left. There is only one way to come in from the top and one way to come in from the left, we can say that there are two ways to reach it:
- 1 1 1
- 1 2 D
- 1 D F
Now, for the right-most D, we can see that there are two ways to come in from the left, and one way to come in from above:
- 1 1 1
- 1 2 3
- 1 D E
Following a similar process for the last two letters, we can map out the number of paths to each spot in the matrix as:
- 1 1 1
- 1 2 3
- 1 3 6
Giving us a final answer of 6.
This pattern should look familiar. It is actually a Pascal's Triangle in a different orientation. With a much larger matrix, we would get (sorry for terrible formatting):
- 1 1 1 1 1 1
- 1 2 3 4 5 6
- 1 3 6 10 15 21
- 1 4 10 20 35 46
- 1 5 15 35 70 116
- 1 6 21 46 116 232
For a Pascal's Triangle, one can simply use a Combination function to find the value for any point in the triangle.
I haven't solved it yet, but for those completely clueless about where to even start, hopefully this helps.
rajneshmalik I implemented your logic but some of test cases are failing. Can you please point out mistake in this.
int solve(int n, int m) { int i,j; int arr[n][m]={0};
for(i=0; i<n; i++) { for(j=0; j<m; j++) { if(i == 0 || j == 0) arr[i][j] = 1; else arr[i][j] = arr[i][j-1] + arr[i-1][j]; } } return arr[n-1][m-1];}
dr0opy check your constraints for this question 1 ≤ m,n ≤ 10^6. you can't take such large matrix
3Murthi Not 46 it's 56. Since 35+21=56
Steady_Bunny Prerequisites to solve this problem
1.fast exponentiation
#define ll long long int #define mod %1000000007 ll fastexpo(ll a, ll n) { ll ret=1; ll b=a; while(n) { if(n&1)ret=(ret*b)mod; //if(n==odd) b=(b*b)mod; n>>=1; // n/=2 } return (ll)ret; }
2.X^(-1) mod(p) can be written as X^(p-2) mod(p)
vikasjha We can skip fast exponentiation, if we know the extended Euclid's Algorithm to find the modulo inversion.
Mohit_Yadav_389 i love extended euclid's algorithm as it takes like no time to calculate MMI of a number;
Mohit_Yadav_389 If anyone want euclid's extended algo; Here we go;
int mmi(int a, int m){ if(a==1)return 1; int e=m; int f=a; int x= 0; int y= 1; unsigned long long u = 1; int v = 0; int q=0,r=0,c=0,d=0; while(f!=1){ q = e/f; r = e%f; c = x- q*u; d = y - q*v; x = u; y = v; u = c; v = d; e = f; f = r; } return (u+m)%m; }
TheCodeHere Here's my code in C++. I hope you find it useful.
int k = 1000000007; long long f(long long a) { if(a<2) return 1; else return (a*f(a-1))%k; } long long modpow(long long base, long long exp, long long modulus) { base %= modulus; long long result = 1; while(exp > 0) { if(exp & 1) result = (result * base) % modulus; base = (base * base) % modulus; exp >>= 1; } return result; } int main() { int t,m,n; cin >> t; while(t--) { cin >> m >> n; long long temp = (f(n-1)%k*f(m-1)%k)%k; temp = modpow(temp,k-2,k); //(f(n)*f(m-1))^(10000000007-2) long long result = (f(n+m-2)%k*temp%k)%k; cout << result << endl; } return 0; }
rajeevbhatt595 Can anyone improve my code, Test cases 5,6,7,8 are timed out:
from math import factorial for _ in range(0, int(raw_input())): m, n = map(int, raw_input().split()) p1 = 1 if (m > n): for i in range(m, m+n-1): p1 = p1 * i print (p1/factorial(n-1))%((10**9)+7) else: for i in range(n, m+n-1): p1 = p1 * i print (p1/factorial(m-1))%((10**9)+7)
leontp587 I'm confused how it can be gauranteed that (n-1)!(m-1)! is not a multiple of p, such that Fermat's Little Theorem applies?
ajs672 p is prime so by definition it cannot be the product of two smaller numbers. Both n and m are smaller than p so the factorial product will never contain p as a factor and thus will never be a multiple of p.
imkrishnaak static int solve(int n, int m) { if(m==1 || n==1) return 1; if(m == n) return 2*solve(n-1,m); return (solve(n,m-1) + solve(n-1,m)); }
Is this logically correct?
shell87301 Passes all TC:
#include <bits/stdc++.h> using namespace std; const int p=1000000007; int n, m, t; long long fmod(long long N) { if (N<2) return 1; else return (N*fmod(N-1))%p; } long long mmi(long long x) { long long result=1, e=p-2; while (e) { if (e & 1) result = (result*x)%p; x = (x*x)%p; e >>= 1; } return result; } int main() { cin >> t; while (t--) { cin >> n >> m; printf("%lld\n", ((fmod(m+n-2)*mmi((fmod(m-1)*fmod(n-1))%p))%p)); } return 0; }
alpha52omega41 Python :D
c = 10**9+7 def fact(n): result = 1 while n >= 2: result = ((result)*(n%c))%c n -= 1 return result def fastEXP(base, exp, modulus): base %= modulus result = 1 while exp > 0: if exp & 1: result = (result * base) % modulus base = (base*base)%modulus exp >>= 1 return result def combinations(x,y): amodc = fact(x+y-2) bmodc = fact(x-1)*fact(y-1) return ((amodc%c)*(fastEXP(bmodc, (c-2), c)))%c T = int(input()) for _ in range(T): x, y = map(int, input().split()) print(combinations(y, x))
Mohit_Yadav_389 this question is equivalent to Project Euler #15 Lattice Points;
Sort 25 Discussions, By:
Please Login in order to post a comment