T756 Cake
原题：（权限限制没有超链接）
题目描述 Description
小杉现在很无聊，于是他想给蛋糕上色。小杉的想法是这样的，他先用刀把蛋糕切成若干块，然后再对每个部分上色（怎么又是上色……）。
小杉的切法是这样的，一共切n次，每次从蛋糕中某一点(不能在蛋糕边缘)下手，然后用刀痕引出两条射线，一直切到蛋糕的边缘。而且小杉很笨，每次都只能切出固定的一种形状，但是每次的形状都把蛋糕切成了尽可能多块。
一个可爱的上色方案应该满足每个区域只能上粉红或天蓝两种颜色（相邻区域可以同色）。
小杉现在想知道总共有多少种可爱的上色方案。
输入输出格式 Input/output
输入格式：
一行一个整数n
输出格式：
仅有一行，一个整数，为上色方案数对19900801取模的结果
输入输出样例 Sample input/output
样例测试点#1
输入样例：
1
输出样例：
4
说明 description
切一次，小杉会把蛋糕切成两个部分，每个部分两种上色可能，一共四种可能(2*2)。
对于100%的数据,0<=n<=5000;
个人解法：
我认为有必要解释一下题意。
其实小杉是这样切蛋糕的。
所谓引两条射线就是这样（端点不能在蛋糕边缘）。然后就把蛋糕分成了很多块（竟然可以切5000刀……还要染色，大雾）。
我们知道，如果蛋糕有n块，那么应该有2^n种可爱的染色方案。
所以接下来就是要求n刀最多把蛋糕切成几块了。
对于这一种切法，我们可以由另一种熟悉的情况演变过来。
如果有n刀，那么显而易见，实际切成的块数fact应该等于下图的方案数imagine1减去n。
所以接下来就是要求n组线段（每组2条）最多把蛋糕切成几块了。
那么，n组线段又可以从n条线段推导出来。
假设n条线段可以把蛋糕分为imagine2块。那么imagine1和imagine2满足的条件应该是
imagine2+add=imagine1，其中add=(3*n^2-n)/2。
为什么是这样呢？
我们看，对于每一条线段，从一条变成一组会增加一些块数，而这些块数正是图中绿色区域。因为除开本条线段之外还有(n-1)条线段，每一条线段都会变成一组，也就是有2*(n-1)条线段会经过这一组线段，所以会把这一组线段分为2*(n-1)+1=2*n-1个部分。
对于每一组线段都如此，那么一共n组先段，就会增加n*(2*n-1)块。
然而我们知道，每组线段相交的地方我们都重复计算了一次。所以我们还要扣除重复计算的。那扣除多少呢？这就是n条线段最多有几个交点了。根据简单的计数原理，我们知道要扣除n*(n-1)/2块。
所以，对于n组线段的解，我们就可以由n条线段的解推出。公式便是：
imagine2+add=imagine1，其中add=(3*n^2-n)/2。
接下来只要求出n条线段最多把蛋糕分为多少块就可以了。
这就很好算了（这有很多算法，我只写一个不要脑子的算法——列表）。
列表如下：
那么就发现了：
a[i]=a[i-1]+i。
其实这也是可以用数学原理推导出来的（我就不写了）。
所以，最后总结出的公式就是——见代码好咯。
当然，我这里想到O(n)的算法就偷懒不想想了。后来仔细想想，其实最后一步完全可以用公式换成O(1)的算法。我就不具体说明了。
代码如下：
const
maxn=19900801;//mod的数
var
i,n,ans:longint;
a:array[0..5000] of longint;
function add(i:longint):longint;//如上所述
begin
exit(((3*sqr(n)-n) div 2) mod maxn);
end;
function func(a,x:longint):longint;//求a^x mod maxn，懒，而且忘记了快速幂，我得去补补
var
vi:longint;
vk:qword;
begin
vk:=1;
for vi:=1 to x do
vk:=vk*a mod maxn;
exit(vk);
end;
begin
read(n);
a[0]:=1;
for i:=1 to n do
a[i]:=(a[i-1]+i) mod maxn;//递推
ans:=(a[n]+add(n)-n) mod maxn;
ans:=func(2,ans);//求答案
writeln(ans);
end.
又一次被数学所折服……如果各位有什么好的意见或建议，欢迎提出。
希望与你们共同进步。