30 lines
881 B
C++
30 lines
881 B
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
// NOI 我就想问一声，这是在赛场临时能想出来的办法吗?
|
||
// https://www.cnblogs.com/bajdcc/p/8972992.html
|
||
|
||
#define M 12345
|
||
|
||
int dp_oushu[10001] = {0};
|
||
int dp_jishu[10001] = {0};
|
||
|
||
int main() {
|
||
//输入+输出重定向
|
||
freopen("../1277.txt", "r", stdin);
|
||
//1位数时，是可以用眼睛看出来结果的，做为动态规划的出发点数据
|
||
dp_oushu[1] = 8;
|
||
dp_jishu[1] = 1;
|
||
int n;
|
||
cin >> n;
|
||
//迭代增加，在上一个数据的基础上进行增加尝试,找出与上一个的关系
|
||
for (int i = 2; i <= n; i++) {
|
||
dp_oushu[i] = (9 * dp_oushu[i - 1] + dp_jishu[i - 1]) % M;
|
||
dp_jishu[i] = (9 * dp_jishu[i - 1] + dp_oushu[i - 1]) % M;
|
||
}
|
||
cout << dp_oushu[n] % M << endl;
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
}
|