|
In how many ways can you tile a xn rectangle by x or x tiles? Here is a sample tiling of a x rectangle
Here is a sample tiling of a x rectangle Input and Output Input is a sequence of lines each line containing an integer number <= n <= For each line of input output one integer number in a separate line giving the number of possible tilings of a xn rectangle Sample Input
Sample Output
题意给定* 和 *的小块要求拼接成 * n有多少种方法 思路假设当前块为 * 剩下为 f(n )种当前为*剩下为f(n )种*有种组合方法所以f(n) = f(n ) + f(n ) * ; 代码 #include <stdioh>#include <stringh>#define max(ab) (a)>(b)?(a):(b)#define min(ab) (a)<(b)?(a):(b)const int N = ;const int MAXBIGN = ; struct bign { int s[MAXBIGN]; int len; bign() { len = ; memset(s sizeof(s)); } bign operator = (const char *number) { len = strlen(number); for (int i = ; i < len; i++) s[len i ] = number[i] ; return *this; } bign operator = (const int num) { char number[N]; sprintf(number %d num); *this = number; return *this; } bign (int number) {*this = number;} bign (const char* number) {*this = number;} bign operator + (const bign &c){ bign sum; int t = ; sumlen = max(this>len clen); for (int i = ; i < sumlen; i++) { if (i < this>len) t += this>s[i]; if (i < clen) t += cs[i]; sums[i] = t % ; t /= ; } while (t) { sums[sumlen++] = t % ; t /= ; } return sum; } bign operator * (const bign &c){ bign sum; bign zero; if (*this == zero || c == zero) return zero; int i j; sumlen = this>len + clen; for (i = ; i < this>len; i++) { for (j = ; j < clen; j ++) { sums[i + j] += this>s[i] * cs[j]; } } for (i = ; i < sumlen; i ++) { sums[i + ] += sums[i] / ; sums[i] %= ; } sumlen ++; while (!sums[sumlen ]) { sumlen ; } return sum; } bign operator (const bign &c) { bign ans; anslen = max(this>len clen); int i; for (i = ; i < clen; i++) { if (this>s[i] < cs[i]) { this>s[i] += ; this>s[i + ]; } anss[i] = this>s[i] cs[i]; } for (; i < this>len; i++) { if (this>s[i] < ) { this>s[i] += ; this>s[i + ]; } anss[i] = this>s[i]; } while (anss[anslen ] == ) { anslen; } if (anslen == ) anslen = ; return ans; } void put() { if (len == && s[] == ) { printf(); } else { for (int i = len ; i >= ; i) printf(%d s[i]); } } bool operator < (const bign& b) const { if (len != blen) return len < blen; for (int i = len ; i >= ; i) if (s[i] != bs[i]) return s[i] < bs[i]; return false; } bool operator > (const bign& b) const { return b < *this; } bool operator <= (const bign& b) const { return !(b < *this); } bool operator >= (const bign& b) const { return !(*this < b); } bool operator != (const bign& b) const { return b < *this || *this < b;} bool operator == (const bign& b) const { return !(b != *this); }};int n;bign save[]; void init() { save[] = ; save[] = ; bign tep = ; for (int i = ; i <= ; i ++) { save[i] = save[i ] + (save[i ] * tep); }} int main() { init(); while (~scanf(%d &n)) { save[n]put(); printf(n); } return ;} |
