XXVI.[FJOI2007]轮状病毒
论此题的一百种不同解法
首先，这题是有通项公式的——
\(f[i]=3f[i-1]-f[i-2]+2\)，
或\(f[i]=i^2-4*[i|2]\)。
当然这并不是我们DP笔记的讨论内容。
可以观察到，答案相当于：
将\(1\)到\(n\)共\(n\)个物品分成一些相邻的组，每组选出一个点，求分组方案数。（注意\(1\)和\(n\)可以在一起）。
我们设\(f[i]\)表示不考虑\(1\)和\(n\)可以在一起的方案数。
则有
\(f[i]=\sum\limits_{j=1}^i f[i-j]*j\)
我们让\(f[i]\)中后\(j\)个数单独分一组，则剩下的是\(f[i-j]\)；这\(j\)个数选出一个点，\(j\)种选法。
现在我们强制\(1\)和\(n\)在一起；
方案数为
\(num=\sum\limits_{i=2}^{n}f[n-i]*i*(i-1)\)
我们选出\(i\)个节点放在两边，共有\(i-1\)种放法；
从中选出一个连到中间，共有\(i\)种选法；
剩下的部分是\(f[n-i]\)。
然后答案即为\(num+f[n]\)。
加上高精度，复杂度\(O(n^3)\)。
另外这个\(f\)是可以通过差分达到线性递推的（当然加上高精度还是\(O(n^2)\)）。
代码：
#include<bits/stdc++.h>
using namespace std;
int n;
struct Wint:vector<int>{
Wint(int n=0)
{
push_back(n);
check();
}
Wint& check(){
while(!empty()&&!back())pop_back();
if(empty())return *this;
for(int i=1; i<size(); ++i)(*this)[i]+=(*this)[i-1]/10,(*this)[i-1]%=10;
while(back()>=10)push_back(back()/10),(*this)[size()-2]%=10;
return *this;
}
}f[110],res;
Wint& operator+=(Wint &a,const Wint &b){
if(a.size()<b.size())a.resize(b.size());
for(int i=0; i!=b.size(); ++i)a[i]+=b[i];
return a.check();
}
Wint operator+(Wint a,const Wint &b){
return a+=b;
}
Wint& operator*=(Wint &a,const int &b){
for(int i=0;i<a.size();i++)a[i]*=b;
return a.check();
}
Wint operator*(Wint a,const int &b){
return a*=b;
}
void print(Wint a){
for(int i=a.size()-1;i>=0;i--)putchar(a[i]+'0');
}
int main(){
scanf("%d",&n);
f[0]=Wint(1),f[1]=Wint(1);
for(int i=2;i<=n;i++)for(int j=1;j<=i;j++)f[i]+=f[i-j]*j;
res=f[n];
for(int i=2;i<=n;i++)res+=f[n-i]*(i*(i-1));
print(res);
return 0;
}