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.
Loading...
  1. Practice
  2. Mathematics
  3. Fundamentals
  4. Sherlock and Permutations
  5. Discussions

Sherlock and Permutations

  • raj_yadav29oct + 3 comments

    Bro i am getting run time error on my c# code can you help me with that-

    static void Main(string[] args)
        {
          
        int t =Convert.ToInt32(Console.ReadLine());
          
            while(t>0)
            {
                string[] data =Console.ReadLine().Split(' ');
                ulong[] data1 = Array.ConvertAll(data, ulong.Parse);
                ulong N = data1[0];
                ulong M = data1[1];
                ulong newM = M - 1;
                ulong topfact = 1;
                ulong belowfact1 = 1;
                ulong belowfact2 = 1;
                ulong result = 0;
                for (ulong i=1;i<=(N+ newM);i++)
                {
                    topfact = topfact * i;
                    if(i<=N)
                    {
                        belowfact1 = (belowfact1 * i);
                    }
                    if (i <= newM)
                    {
                        belowfact2 = belowfact2 * i;
                    }
                }

                result = (topfact / (belowfact1 * belowfact2))%1000000007;


                    Console.WriteLine(result);
                t--;
            }
            Console.Read();
        }
    • bazuka_ + 1 comment

      Actually the answer is

      (m+n-1)C(n)=(m+n-1)!/ ((m-1)!)*n!)

      and the forumula

      Ncr=(n-1)c(r-1)+ (n-1)c(r)

      now you can apply dp you may take help of this function as it is little bit tuff for me to understand c# that's why iam writing this function

      `cpp

      for (i = 0; i <= n; i++) { for (j = 0; j <= k; j++) {

              if (j == 0 || j == i)//as nc0=ncn=1;
            C[i][j] = 1;


     else
       C[i][j] = ((C[i-1][j-1])%mod +( C[i-1][j])%mod)%mod;
    }
}

      `

      now you can return the desired answer .

      Now in your code this line

      result = (topfact / (belowfact1 * belowfact2))%1000000007; will get run-time error or tle as your modulus approach formula is not correct as

      (a * b) % mod = ((a % mod) * (b % mod)) % mod, (a / b ) % mod = ((a % mod) * (b^-1 % mod)) % mod,

      and one more reason is that the

      (topfact / (belowfact1*belowfact2))

      will not work properly .

      if problem persist then feel free to contact for further

      clarification or you may take help of my c code

      http://ideone.com/knhd1k

      ....

      • tamim447 + 0 comments

        k means m..?

    • vishu006 + 0 comments

      Hey take a look at this if it helps

      from math import factorial

n=int(raw_input())
for i in range(n):
    a,b=map(int,raw_input().split())
    print (factorial(a+b-1)/(factorial(a)*factorial(b-1)))%1000000007
    • g_sosacuervo1 + 0 comments

      I believe if you try with N=1000 and M=1000, you will get the run time error. Basically, 1000!*999>ulong.MAX, in other words, it should give you kind of overflow.