简答题
偏难
#7465
奶牛散步 从一个无限大的矩阵的中心点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法? 时间限制:10000 内存限制:13107…
奶牛散步
从一个无限大的矩阵的中心点出发,一步只能向右走、向上走或向左走。恰好走N步且不经过已走的点共有多少种走法?
时间限制:10000
内存限制:131072
输入
一个数字,代表N,N<=1000
输出
输出有多少方案数模12345
样例输入
2
样例输出
7
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">// 上一步向上走,下一步可以向左、右、上
// 上一步向左走,下一步可以向左、上
// 上一步向右走,下一步可以向右、上
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long lr = 2, up = 1;
int i = 0;
long long tmplr = 0, tmpup = 0;
if (n == 1) {
cout << 3;
} else {
for (i = 2; i <= n; i++) {
tmplr = lr;
tmpup = up;
lr = (tmpup * 2 + tmplr) % 12345;
up = (tmpup + tmplr) % 12345;
}
cout << (up + lr) % 12345;
}
return 0;
}</pre>
这道题暂未补解析。