﻿ 10359 - Tiling （遞推，類斐波那契）_電腦知識網

10359 - Tiling （遞推，類斐波那契）

2022-06-13   來源: Web編程

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 ; }

From:http://tw.wingwit.com/Article/program/Web/201405/30987.html