尼玛。。 一个 long long 调了 两天 。。
解题：
我们 可以沿着某一条从1到n的路线走下去，看能否找到合适的答案。。
剪枝就是：
1： 走过的不在走 记忆话搜索。。
2: 如果某一点不是k的约数或者大于k或者和前面相等，不在往下走。。
注意：因为k的约数的范围可能特别大，数组放不下，所以用map哈希。。
用vector建立邻接表。。
View Code
#include<iostream> #include<string.h> #include<stdio.h> #include<algorithm> #include<map> #include<vector> #include<cmath> #define mod 1000000007 using namespace std; typedef long long ll; const int maxn=2005; map<ll,int>node; int n,m; int k; ll dp[maxn][maxn];//就是这个ll ll mm[maxn]; vector<int>gg[maxn]; int pos; void hash(int d) { int p=(int)sqrt(1.0*d); pos=1; for(int i=1;i<p;i++) if(d%i==0) node[i]=pos++,node[d/i]=pos++; if(d%p==0)node[p]=pos; } ll gcd(ll a,ll b) { if(a<b) a=a+b,b=a-b,a=a-b; while(b) { ll temp=a; a=b; b=temp%b; } return a; } ll lcm(ll a,ll b) { return a*b/gcd(a,b); } ll dfs(int u,ll x) { if(dp[u][node[x]]) return dp[u][node[x]]; if(u==n) return x==k; for(int i=0;i<gg[u].size();i++) { if(k%mm[gg[u][i]])continue; ll temp=lcm(x,mm[gg[u][i]]); if(node[temp]!=0&&temp!=x&&temp<=k) //if(temp==x||temp>k)continue; dp[u][node[x]]+=dfs(gg[u][i],temp)%mod; } return dp[u][node[x]]%mod; } int main() { while(scanf("%d%d%d",&n,&m,&k)!=EOF) { // cout<<n<<" "<<m<<" "<<k<<endl; node.clear(); for(int i=0;i<=n;i++) gg[i].clear(); for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); gg[u].push_back(v); } for(int i=1;i<=n;i++) scanf("%lld",&mm[i]); hash(k); memset(dp,0,sizeof(dp)); ll ans=dfs(1,mm[1]); printf("%lld\n",ans); } return 0; }