[TIOJ] 1107. 繁複的二元樹

題目連結:http://tioj.infor.org/problems/1107
裸卡特蘭數題,而卡特蘭數可由$C_0=1$及$C_{n+1}=\frac{2(2n+1)}{n+2} \times C_{n}$的遞迴關係式算出,不過本題要輸出成科學記號有點麻煩,記得處理一下ww
#include <bits/stdc++.h>
using namespace std;
#define N 1000000

struct sciF{
		double _a;
		int _n;
		inline sciF operator=(int x){
			_a=x;
			_n=0;
			while(_a>10){
				_n++;
				_a/=10.;
			}
			return *this;
		}
		inline sciF operator*(int x){
			_a*=x;
			while(_a>10){
				_n++;
				_a/=10.;
			}
			return *this;
		}
		inline sciF operator/(int x){
			_a/=x;
			while(_a<1){
				_n--;
				_a*=10.;
			}
			return *this;
		}
};
bitset<N+5> isset;
sciF cc[N+5];

sciF cat(int);

int main(){
	int n;scanf("%d",&n);
	cc[0]=1;
	isset[0]=1;
	for(int i=1;i<=N;i++)cat(i);
	while(n!=0){
		sciF ans=cat(n);
		printf("%0.3lfE+%d\n",ans._a,ans._n);
		scanf("%d",&n);
	}
	return 0;
}

sciF cat(int n){
	if(!isset[n]){
		sciF xx=cat(n-1) * 2 *(2*(n-1)+1);
		xx=xx/((n-1)+2);
		cc[n]=xx;
	}
	isset[n]=1;
	return cc[n];
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology