前言：
日月如梭，光阴似箭。大家好，我盛艺承又回来了。今天给大家讲一下纪中的DP（递推）真题。
题目描述
在网格中取一个N x 1的矩形，并把它当作一个无向图。这个图有2(N+1)个顶点，有3(N-1)+4条边。这个图有多少个生成树？答案 mod 12345 后输出。
思路：
这一题应该算比较水的了吧。。。。。。只要推出了递推式就能做出来了
这里我们就直接推了吧。
我们通过枚举，不难发现——
n=1时 4
n=2时 15
n=3时 56
n=4时 209
只用枚举4个就够了。
通过这4组样例，我们不难发现——f[i]=f[i-1]*4-f[i-2]。也就是说，目前f的第i项，等于f的i-1项*4-f的i-2项。
当然，这只是递推公式。还要把他得到的答案%12345（题目说的）。
不过你这样做了以后呢，也得不到100分。为什么呢？因为有可能f[i-1]*4-f[i-2]为负数。那样的话就完犊子了。所以我们为了防止这种事情发生，我们给他+12345。这样就可以保证不会出现负数了。
为什么呢？因为，如果答案就是负数，加上12345后，就相当于给了他一个绝对值。而如果他是正数的话，后面还有一个%12345呢，也没有关系。
下面是代码：
#include<bits/stdc++.h>
using namespace std;
int f[10005]={1,4},i,n;//f数组用来计算出当前的第f[i]项的值为多少。
int main(){
cin>>n;
for(i=2;i<=n;i++) f[i]=(f[i-1]*4-f[i-2]+12345)%12345;//用一个for循环来求出当前第f[i]的值为多少。
cout<<(f[n])%12345;//输出时别忘记%12345啊！
}