Блог пользователя deinier

Help need with Catalan series.
Автор deinier, 13 лет назад, По-английски

Hi, everyone. I want to know if the i — term (mod 1000000007) to the Catalan series could be calculated by this way. Do you, please, can explain me, if this way I get the answer by dp or if I need to do other thing? Thanks everybody. 

fact[1][1] = 1;
for(i=2;i<=1000;i++)
 {
   for(j=1;j<=i;j++)
    {
      if(j == 1)
        fact[i][1] = 1;
      else
       {
         if(i == j)
           fact[i][j] = fact[i][j-1] + fact[i-1][j-1];
         else
           fact[i][j] = fact[i][j-1] + fact[i-1][j];
         fact[i][j] %= 1000000007;
       }
    }
 }
  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Catalan series can be calculated as , so you can fo anything you do with binomial coefficients, good luck!

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks, man, I read about that too, but I need to know too what is the problem to use this way because I think it give me the numbers too. I appreciate your help. I will study with binomial coefficients.

    → Ответить
    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится

      You should know that C2nn is in fact , so you can calculate both parts (take reminder of both) and divide first by second. Get reminder of such operation you can using your math, or simply multiply them and reverse element.

      Sorry for poor English, but I don't know how to explain it in English

      → Ответить
»
13 лет назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

Some days ago i was thinking about it. And i made my own code:

long Catalan(int n) {
        long res = C(2*n, n);
	res /= n + 1;
	return res;
}

long C(int n, int k) {
	long res = 1;
	for (int i = 1; i <= k; i++)
		res = res * (n - k + i) / i;
	return res;
}

As you can see, for calculating Catalan series I chose formula .
And for calculating Cnk I chose optimazed realization of standart algorithm.
I think my code may help you. If not, I won't be offended :) Have a good time :)

→ Ответить
  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Thanks man, I appreciate that too. I will try to prove my solution in other exercise. Have a nice day!!!

    → Ответить