表示我这种蒟蒻面对这种递推第一思想显然是打表啊
先贴个用来打表的暴力：
#include <cstdio>
struct node
{
int l,r;
}p[];
bool used[];
int f[];
int n,cnt,cct;
int findf(int x)
{
if(x==f[x])
{
return x;
}
return f[x]=findf(f[x]);
}
bool check()
{
for(int i=;i<=n+;i++)
{
f[i]=i;
}
for(int i=;i<=cct;i++)
{
if(used[i])
{
int f1=findf(p[i].l);
int f2=findf(p[i].r);
f[f2]=f1;
}
}
int ff=;
for(int i=;i<=n+;i++)
{
int f1=findf(i);
if(!ff)
{
ff=f1;
}else if(ff!=f1)
{
return ;
}
}
return ;
}
void dfs(int dep,int tot)
{
if(dep==cct+)
{
if(tot==n)
{
if(check())
{
cnt++;
}
}
return;
}
used[dep]=;
dfs(dep+,tot+);
used[dep]=;
dfs(dep+,tot);
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n+;i++)
{
p[++cct].l=;
p[cct].r=i;
}
for(int i=;i<=n+;i++)
{
if(i==n+)
{
p[++cct].l=i;
p[cct].r=;
}else
{
p[++cct].l=i;
p[cct].r=i+;
}
}
dfs(,);
printf("%d\n",cnt);
return ;
}
/*
1 1
2 5
3 16
4 45
5 121
6 320
*/
实测这个打表程序是正确的（可以获得30分）
接下来是本人心路历程：
观察一下：1-1,2-5,3-16,4-45...找一下前后项吧！
观察前后项的倍数关系应该在2~3之间，那先定一个基础表达式
f[i]=2f[i-1]+...或f[i]=3f[i-1]+...
如果系数用2，发现剩下的部分长这样啊...
f[3]=2f[2]+6
f[4]=2f[3]+13
f[5]=2f[4]+31
...
好像后面的没啥规律...
那换系数用3！
f[4]=3f[3]-3
f[5]=3f[4]-14
...
好像也没啥啊...
等一下！
-3=-5+2
-14=-16+2
如果下面再写下来，应该是-43=-45+2！
这不就找出来了吗！
f[i]=3f[i-1]-f[i-2]+2!
于是敲个高精度这题就结束了...
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
struct Bignum
{
int a[10005];
int ilen;
}f[105],zero;
int n;
Bignum add(Bignum x)
{
Bignum ret=x;
ret.a[1]+=2;
int i=1;
while(ret.a[i]>=10)
{
ret.a[i+1]+=ret.a[i]/10;
ret.a[i]%=10;
i++;
}
if(ret.a[ret.ilen+1])
{
ret.ilen++;
}
return ret;
}
Bignum mul(Bignum x)
{
Bignum ret=zero;
for(int i=1;i<=x.ilen;i++)
{
ret.a[i]+=3*x.a[i];
ret.a[i+1]+=ret.a[i]/10;
ret.a[i]%=10;
}
ret.ilen=x.ilen;
while(ret.a[ret.ilen+1])
{
ret.ilen++;
}
return ret;
}
Bignum sub(Bignum x,Bignum y)
{
Bignum ret=zero;
for(int i=1;i<=y.ilen;i++)
{
ret.a[i]+=x.a[i]-y.a[i];
if(ret.a[i]<0)
{
ret.a[i]+=10;
ret.a[i+1]--;
}
}
for(int i=y.ilen+1;i<=x.ilen;i++)
{
ret.a[i]+=x.a[i];
}
ret.ilen=x.ilen;
while(!ret.a[ret.ilen]&&ret.ilen>1)
{
ret.ilen--;
}
return ret;
}
int main()
{
scanf("%d",&n);
f[1].a[1]=1;
f[1].ilen=1;
f[2].a[1]=5;
f[2].ilen=1;
f[3].a[1]=6;
f[3].a[2]=1;
f[3].ilen=2;
for(int i=4;i<=n;i++)
{
f[i]=mul(f[i-1]);
f[i]=add(f[i]);
f[i]=sub(f[i],f[i-2]);
}
for(int i=f[n].ilen;i>=1;i--)
{
printf("%d",f[n].a[i]);
}
printf("\n");
return 0;
}