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
