BZOJ 1002 FJOI2007 轮状病毒 递推+高精度

时间：2023-03-08 16:23:14
BZOJ 1002 FJOI2007 轮状病毒 递推+高精度

题目大意：轮状病毒基定义如图。求有多少n轮状病毒

这个递推实在是不会……所以我选择了打表找规律

首先执行下面程序

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define M 110

using namespace std;

struct abcd{

	int to,next;

	bool ban;

}table[M<<2];

int head[M],tot=1;

int n,ans;

void Add(int x,int y)

{

	table[++tot].to=y;

	table[tot].next=head[x];

	head[x]=tot;

}

int fa[M],v[M],q[M],r,h;

bool BFS()

{

	int i;

	r=h=0;

	memset(v,0,sizeof v);

	memset(fa,-1,sizeof fa);

	q[++r]=0;

	while(r!=h)

	{

		int x=q[++h];

		for(i=head[x];i;i=table[i].next)

			if(!table[i].ban)

			{

				if(table[i].to==fa[x])

					continue;

				if(v[table[i].to])

					return 0;

				fa[table[i].to]=x;

				v[table[i].to]=1;

				q[++r]=table[i].to;

			}

	}

	if(r<=n)

		return 0;

	return 1;

}

void DFS(int x)

{

	if(x+x>tot)

	{

		if( BFS() )

			++ans;

		return ;

	}

	table[x<<1].ban=table[x<<1|1].ban=0;

	DFS(x+1);

	table[x<<1].ban=table[x<<1|1].ban=1;

	DFS(x+1);

}

int main()

{

	int i;

	while(1)

	{

		memset(head,0,sizeof head);

		tot=1;ans=0;

		cin>>n;

		for(i=1;i<=n;i++)

			Add(0,i),Add(i,0),Add(i,i%n+1),Add(i%n+1,i);

		DFS(1);

		cout<<ans<<endl;

	}

}

够简单。够暴力吧

然后打表。1~14的答案例如以下

1 5 16 45 121 320 841 2205 5776 15125 39601 103680 271441 710645

奇数项

1 16 121 841 5776 39601 271441

开根号得

1 4 11 29 76 199 521

a[i]=a[i-1]*3-a[i-2]

偶数项

5 45 320 2205 15125 103680 710645

除以5得

1 9 64 441 3025 20736 142129

开根号得

1 3 8 21 55 144 377

a[i]=a[i-1]*3-a[i-2]

然后高精度递推即可了

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

struct abcd{

    int x[100],cnt;

    int& operator [] (int y)

    {

        return x[y];

    }

    void operator = (int y)

    {

        x[1]=y;

        cnt=1;

    }

}f[100];

abcd operator - (abcd x,abcd &y)

{

    int i;

    abcd z=f[0];

    z.cnt=max(x.cnt,y.cnt);

    for(i=1;i<=z.cnt;i++)

    {

        z[i]+=x[i]-y[i];

        if(z[i]<0)

            z[i+1]--,z[i]+=10;

    }

    while(z.cnt&&!z[z.cnt])

        z.cnt--;

    return z;

}

abcd operator * (abcd &x,abcd &y)

{

    int i,j;

    abcd z=f[0];

    for(i=1;i<=x.cnt;i++)

        for(j=1;j<=y.cnt;j++)

            z[i+j-1]+=x[i]*y[j],z[i+j]+=z[i+j-1]/10,z[i+j-1]%=10;

    z.cnt=x.cnt+y.cnt;

    if(!z[z.cnt])

        --z.cnt;

    return z;

}

abcd operator * (abcd x,int y)

{

    int i;

    abcd z=f[0];

    for(i=1;i<=x.cnt;i++)

        z[i]+=x[i]*y,z[i+1]+=z[i]/10,z[i]%=10;

    z.cnt=x.cnt;

    if(z[z.cnt+1])

        ++z.cnt;

    return z;

}

ostream& operator << (ostream &os,abcd x)

{

    int i;

    for(i=x.cnt;i;i--)

        os<<x[i];

    return os;

}

int n;

int main()

{

    int i;

    cin>>n;

    f[1]=1;

    f[2]=n&1?4:3;

    for(i=3;i+i<=n+1;i++)

        f[i]=f[i-1]*3-f[i-2];

    cout<<f[n+1>>1]*f[n+1>>1]*(n&1?1:5)<<endl;

}

相关文章