求一道递推题在线deng很ji！

Question

Description
在网格中取一个N x 1的矩形，并把它当作一个无向图。这个图有2(N+1)个顶点，有3(N-1)+4条边。这个图有多少个生成树？

Input
多组数据，每行一个数N（N<=1000）
Output
每行输出一个数，答案mod12345
Sample Input
1
Sample Output
4

Answer 1

#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啊！
}