A32871. 奶牛散步从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？ 输入一个数字，代表N,N<=1000输出输出有多少方案数模12345样例输入2样例输出7
填空题
较难
知识点
题目描述
奶牛散步
从一个无限大的矩阵的中心点出发，一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法？
输入
一个数字，代表N,N<=1000
输出
输出有多少方案数模12345
样例输入
2
样例输出
7
参考答案
#include<algorithm>
#include<cstdio>
using namespace std;
int n, f[1005][5];
int main()
{
scanf("%d", &n);
f[1][1] = 1;
f[1][2] = 1;
f[1][3] = 1;
f[1][4] = 3;
for(int i = 2;i <= n;i++)
{
f[i][1] = (f[i - 1][1] + f[i - 1][3]) % 12345;
f[i][2] = (f[i - 1][2] + f[i - 1][3]) % 12345;
f[i][3] = (f[i - 1][1] + f[i - 1][2] + f[i - 1][3])%12345;
f[i][4] = (f[i][1] + f[i][2] + f[i][3])%12345;
}
printf("%d", f[n][4]);
return 0;
}
上一题
下一题