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

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

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
  • Проголосовать: не нравится

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

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

→ Ответить
»
14 лет назад, скрыть # |
← 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 :)

→ Ответить