c731. 走路時要算數學

題目 Problem

題目連結：https://zerojudge.tw/ShowProblem?problemid=c731

敘述 Description

在一個二維平面上，從原點出發，每一步等於一單位長，每一次只能向右走、向上走或向左走。請問恰好走 n 步且不經過已走的點共有多少種走法？

輸入 Input

輸入僅一行，為正整數 n （ 0 < n <= 10000 ）。

輸出 Output

一個整數, 表示方案數。由於答案可能很大，你只需要輸出這個答案 mod 12345的值 ( 換句話說，輸出這個答案除以12345的餘數 )。

範例輸入 Sample Input

【範例輸入一】
2

【範例輸入二】
1

範例輸出 Sample Output

【範例輸出一】
7

【範例輸出二】
3

提示 Hint

【分數】

20% n <= 5

40% n <= 10

60% n <= 100

80% n <= 1000

100% n <= 10000

題解 Solution

經典DP問題，如果不要走到重複的點，就不要往回走
如果要往上走，不用考慮會不會重複的點，全部加起來就對了
如果要往左走，前一步就不能往右走。
如果要往右走，前一步就不能往左走。
然後記得每次算完 $Mod\ 12345$ 就好

程式碼 Accepted Code

#include <bits/stdc++.h>
#define _ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
int main(){
	int up[10001]={1},left[10001]={1},right[10001]={1};
	int N;
	cin>>N;
	for(int i=1;i<N;i++){
		up[i]=up[i-1]+left[i-1]+right[i-1];
		left[i]=up[i-1]+left[i-1];
		right[i]=up[i-1]+right[i-1];
		up[i]%=12345;
		left[i]%=12345;
		right[i]%=12345;
	}
	cout<<(up[N-1]+left[N-1]+right[N-1])%12345<<'\n';
	return 0;
}