題目 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;
}
後記 Afterword#
數字應該能再開大一點啊，還以為這題有什麼陷阱 = = 如果沒有意外，下一篇應該是寫演講筆記 以前演講聽一聽就算了，不過這次我想寫出來 講者是誰？敬請期待