[TIOJ] 1557. 馬可波羅的奇想曲

題目連結:http://tioj.infor.org/problems/1557

---

邊DFS邊DP，只要知道起點到起點的走法是一種，然後每次都詢問他的來源走法有幾種，大概這樣吧

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define PB push_back
#define N 10000
#define modBASE 1073741824

vector<int> graph[N + 10];
lld val[N + 10]={0};
bitset<N + 10>dped;
lld dp(int);

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		graph[b].PB(a);
	}
	int Start,End;
	scanf("%d%d",&Start,&End);
	val[Start]=1;
	dped[Start]=1;
	lld ans = dp(End);
	printf("%lld",ans);
	return 0;
}

lld dp(int w){
	if(!dped[w]){
		lld sum=0;
		for(int i=0;i<graph[w].size();i++){
			sum += dp(graph[w][i]);
			sum %= modBASE;
		}
		val[w]=sum;
		dped[w]=1;
	}
	return val[w];
}