uva 10862 uva 10334 uva 10359 uva 10918 （大数+递推）

10334是fib，不说了。

10862：

题意：

给n个房子，让他们和一个信号站连，求连法。

解析：

设f[n]代表n个房子的连法。

???????????? O

房子堆n-1? 房子n

到达当前决策n时，房子n可以连圈，则此时连法是f[n -1]，可以连房子堆n-1，连法也是f[n - 1]。

还有一种连法就是房子n与房子n-1，圈圈O都相连，此时影响到前面的决策，即房子n-2不能与O相连，则连法f[n -1 ] - f[n - 2]。

和：3 * f[n-1] - f[n-2]

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <climits>
#include <cassert>
using namespace std;

#define maxn 30000

struct bign
{
    long long len,s[maxn];

    bign()
    {
        memset(s,sizeof(s));
        len = 1;
    }

    bign(long long num)
    {
        *this = num;
    }

    bign(const char* num)
    {
        *this = num;
    }

    bign operator = (long long num)
    {
        char s[maxn];
        sprintf(s,"%d",num);
        *this = s;
        return *this;
    }

    bign operator = (const char* num)
    {
        len = strlen(num);
        for (long long i = 0; i < len; i++) s[i] = num[len-i-1] - '0';
        return *this;
    }

    string str() const
    {
        string res = "";
        for (long long i = 0; i < len; i++) res = (char)(s[i] + '0') + res;
        if (res == "") res = "0";
        return res;
    }

    /*去除前导0*/
    void clean()
    {
        while(len > 1 && !s[len-1]) len--;
    }

    /*高精度的加法*/
    bign operator + (const bign& b) const
    {
        bign c;
        c.len = 0;
        for (long long i = 0,g = 0; g || i < max(len,b.len); i++)
        {
            long long x = g;
            if (i < len) x += s[i];
            if (i < b.len) x += b.s[i];
            c.s[c.len++] = x % 10;
            g = x / 10;
        }
        return c;
    }

    /*高精度的减法*/
    bign operator - (const bign& b)
    {
        bign c;
        c.len = 0;
        for (long long i = 0,g = 0; i < len; i++)
        {
            long long x = s[i] - g;
            if (i < b.len) x -= b.s[i];
            if (x >= 0)
                g = 0;
            else
            {
                g = 1;
                x += 10;
            }
            c.s[c.len++] = x;
        }
        c.clean();
        return c;
    }

    /*高精度的乘法*/
    bign operator * (const bign& b)
    {
        bign c;
        c.len = len + b.len;
        for (long long i = 0; i < len; i++)
            for (long long j = 0; j < b.len; j++)
                c.s[i+j] += s[i] * b.s[j];
        for (long long i = 0; i < c.len-1; i++)
        {
            c.s[i+1] += c.s[i] / 10;
            c.s[i] %= 10;
        }
        c.clean();
        return c;
    }

    /*高精度除以低精度*/    /*用到除法和取余的时候可能需要把全局的int替换成long long*/
    bign operator / (long long b) const
    {
        assert(b > 0);
        bign c;
        c.len = len;
        for (long long i = len-1,g = 0; i >= 0; --i)
        {
            long long x = 10*g+s[i];    //这里可能会超过int 故用long long

            c.s[i] = x/b;                //这里可能会超过int

            g = x-c.s[i]*b;                //这里可能会超过int
        }
        c.clean();
        return c;
    }

    /*高精度对低精度取余*/    /*用到除法和取余的时候可能需要把全局的int替换成long long*/
    bign operator % (long long b)
    {
        assert(b > 0);
        bign d = b;
        bign c = *this-*this/b*d;
        return c;
    }

    bool operator < (const bign& b) const
    {
        if (len != b.len) return len < b.len;
        for (long long i = len-1; i >= 0; i--)
            if (s[i] != b.s[i]) return s[i] < b.s[i];
        return false;
    }

    bool operator > (const bign& b) const
    {
        return b < *this;
    }

    bool operator <= (const bign& b)
    {
        return !(b > *this);
    }

    bool operator >= (const bign& b)
    {
        return !(b < *this);
    }

    bool operator == (const bign& b)
    {
        return !(b < *this) && !(*this < b);
    }

    bool operator != (const bign& b)
    {
        return (b < *this) || (*this < b);
    }

    bign operator += (const bign& b)
    {
        *this = *this + b;
        return *this;
    }
};

istream& operator >> (istream &in,bign& x)
{
    string s;
    in >> s;
    x = s.c_str();
    return in;
}

ostream& operator << (ostream &out,const bign& x)
{
    out << x.str();
    return out;
}

bign f[2000 + 10];
void init()
{
    f[1] = 1,f[2] = 3;
    bign three = 3;
    for (int i = 3; i <= 2000; i++)
        f[i] = three * f[i - 1] - f[i - 2];
}

int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    init();
    int n;
    while (cin >> n && n)
        cout << f[n] << endl;
}

10359：

题意：

用1*1和1*2的瓷砖，问能贴几个n*2的方格。

解析：

当前格，加1格得到：f（n-1）种方法，加2格得到：2 * f（n-2）种方法。

0的时候输出1，。。。。。。。。。。。。。。。。。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <climits>
#include <cassert>
using namespace std;

#define maxn 30000

struct bign
{
    long long len,const bign& x)
{
    out << x.str();
    return out;
}

bign f[250 + 10];
void init()
{
    f[0] = 1;
    f[1] = 1,f[2] = 3;
    bign two = 2;
    for (int i = 3; i <= 250; i++)
        f[i] = two * f[i - 2] + f[i - 1];
}

int main()
{
#ifdef LOCAL
    freopen("in.txt",stdin);
#endif
    init();
    int n;
    while (cin >> n)
        cout << f[n] << endl;
}

10918：

题意：

给n，求用1*2的瓷砖有多少种方法能谱n*3的矩形。

解析：

奇数无解，当前选择，由n-2的瓷砖得来，有3 * f（n-2）种方法，若由n-4的瓷砖得来（f（n-2） - f（n-4））种方法。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <climits>
#include <cassert>
using namespace std;

#define maxn 30000

struct bign
{
    long long len,const bign& x)
{
    out << x.str();
    return out;
}

bign f[30 + 10];
void init()
{
    f[0] = 1;
    f[2] = 3;
    bign four = 4;
    for (int i = 4; i <= 30; i++)
        f[i] = four * f[i - 2] - f[i - 4];
}

int main()
{
#ifdef LOCAL
    freopen("in.txt",stdin);
#endif
    init();
    int n;
    while (cin >> n && n != -1)
        cout << f[n] << endl;
}