多米诺骨牌 DOMINO

【题目描述】

Jzabc对多米诺骨牌有很大的兴趣，然而他的骨牌比较特别，只有黑的和白的。他觉得如果存在连续三个骨牌是同种颜色的，那这个骨牌排列就是不美观的。现在他有N个骨牌要排列，他想知道不美观的排列的个数。他想请你帮忙进行统计不美观排列的个数。

【输入格式】

只有一个正整数，即要排列的骨牌的个数。

【输出格式】

一个数，即不美观的排列的个数。

【输入样例】

4

【输出样例】

6

解释：有6中不美观的排列。

【数据规模】

对于20%的数据，满足N<=60

对于50%的数据，满足N<=600

对于100%的数据，满足N<=20000

一开始不会 就没再做

后来小伙伴们提醒了一下有规律

于是打表1-10

发现G(i+1)可以由Gi*2+一个具有斐波那契数列性质的数列中某一项推出

所以递推出的Gi

由于数据太大 用到了压8位高精度

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[4][811];
int z[811];
int m,n=1,a,b,c;

void print(int s[811])
{
    int a;
    for(a=800;a>1;a--)if(s[a])break;
    cout<<s[a];a--;
    while(a)
    {
        if(s[a]<10000000)cout<<'0';
        if(s[a]<1000000)cout<<'0';
        if(s[a]<100000)cout<<'0';
        if(s[a]<10000)cout<<'0';
        if(s[a]<1000)cout<<'0';
        if(s[a]<100)cout<<'0';
        if(s[a]<10)cout<<'0';
        cout<<s[a];
        a--;
    }
}

void jinwei(int s[811])
{
    int a;
    for(a=1;a<=800;a++)
    if(s[a]>99999999)
    {
        s[a+1]=s[a+1]+s[a]/100000000;
        s[a]%=100000000;
    }
}

void addf()
{
    int a;
    n++;
    n%=3;
    int l=(n-2+3)%3;
    int r=(n-1+3)%3;
    for(a=1;a<=800;a++)f[n][a]=f[l][a]+f[r][a];
    jinwei(f[n]);
}

void cheng()
{
    int a;
    for(a=1;a<=800;a++)z[a]*=2;
    jinwei(z);
}

void jia()
{
    int a;
    for(a=1;a<=800;a++)z[a]+=f[n][a];
    jinwei(z);
}

int main()
{
    freopen("domino.in","r",stdin);
    freopen("domino.out","w",stdout);
    scanf("%d",&m);
    if(m<3)
    {
        cout<<0<<endl;
        return 0;
    }
    z[1]=2;
    f[0][1]=0;
    f[1][1]=2;
    
    for(a=4;a<=m;a++)
    {
        addf();
        cheng();
        jia();
    }
    print(z);
    return 0;
}
        

考虑美观的情况，设f[i]为i个骨牌的排列中完美排列的数量。若在第i个位置上放与i-1个骨牌颜色相同的骨牌，则情况数为f[i-2]，否则为f[i-1]，那么f[i]:=f[i-1]+f[i-2]。由二进制的数量可得，此时不完美排列个数即为g[i]:=2^n-f[i]。

这个想法简直是dbl...瞬间就跪烂了

我的理解是

当i与i-1颜色不同时

不会影响完美排列数 所以f[i]=f[i-1]

当颜色相同时

就有可能影响到完美排列

i-3i-2 i-1i

X0 11这种情况下 f[i]=f[i-1]=f[i-2]  因为从i-1到i颜色相同 i-1和i对f[i]没做出贡献 与f[i-2]相比 f[i]既没增加也没减少 

X1 11这种情况下f[i]=f[i-2]  因为从i-2到i颜色相同 i-1和i对f[i]没做出贡献 与f[i-2]相比 f[i]既没增加也没减少

所以f[i]=f[i-1]+f[i-2]

不完美的就是2^n-f[i]

Orz