T758 Valentine’s Seat
原题：（权限限制没有链接）
题目描述 Description
今天是情人节的前一天，小杉还在电影院打工（惨啊…）。
老板很懂得情人节的情调，要小杉提前做好准备，那么现在给小杉的任务是对电影院的座椅上色。
电影院总共n+1行m+1列的椅子排成一个矩阵。第一行的椅子已经全部上了粉红色，第一列从第二个开始的椅子已经全部上了天蓝色。
一个可爱的上色方案应该满足除了第一行第一列以外，对任意的一个椅子，它的颜色应当和它左边的一把椅子（同行）或上面的一把椅子（同列）颜色相同。
小杉现在想知道总共有多少种可爱的上色方案。
输入输出格式 Input/output
输入格式：
一行两个整数n,m(1<=n,m<=3000)
输出格式：
仅有一行，一个整数，为上色方案数对19900801取模的结果
输入输出样例 Sample input/output
样例测试点#1 输入样例：
1 1
输出样例：
2
说明 description
唯一可上色的一把椅子，不是粉红就是天蓝，怎样都是可爱的
n<=3000
个人解法：
这么说来应该每一个椅子f[i,j]，应该有两种选择方案，一种是与f[i-1,j]相同，另一个是与f[i,j-1]相同。
所以f[i,j]=f[i-1,j]+f[i,j-1]。想必不用想多了。
就这样愉悦地AC了。
代码如下：
const
maxn=19900801;
var
i,j:longint;
n,m:longint;
f:array[0..3010,0..3010] of qword;
begin
read(n,m);
for i:=1 to m do
f[i,0]:=1;
for j:=1 to n do
f[0,j]:=1;//初始化
for i:=1 to m do
for j:=1 to n do
f[i,j]:=(f[i-1,j]+f[i,j-1]) mod maxn;//DP方程
writeln(f[i,j] mod maxn);
end.
虽然题目挺简单……但还是很有情调的哈！