【组合数学】Critical Mass, UVa580
刘汝佳书上分析得很好。我就不多写了。
#include<bits/stdc++.h>
using namespace std;
int n;typedef long long LL;
LL f[40],g[40],w[40];
int main()
{
ios::sync_with_stdio(false);
f[0] = f[1] = f[2] = 0;
g[0] = 1;g[1] = 2;g[2] = 4;w[0] = 1;
for(int i=1;i<=30;i++)
w[i]=w[i-1]*2;
for(int i=3;i<=30;i++)
{
f[i] = w[i-3];
for(int j=2;j<=i-2;j++)
f[i]+=g[j-2]*w[i-j-2];
g[i] = w[i]-f[i];
}
while(cin>>n)
{
if(!n)break;
cout<<f[n]<<endl;
}
return 0;
}