)
D https://codeforces.com/contest/2176/problem/D
哎哎，经典的赛后过题。分享D的另一种不同的思路。
Hint1 首先可以观察到除了单独一条边成斐波那契数列的情况，其它更长的数列情况中，除了作为开头的两个点，其它的点都是严格单调递增的。
根据这个这个观察我们可以把图上原来{u,v}(ta[u]<ta[v])的边删除。这样就变成有向无环图了。
再运用dfs回溯+dp(可以参考代码理解)，最后再加上单独一条边成斐波那契数列的情况就可以了。
附上代码
/* by 01022.hk - online tools website : 01022.hk/zh/regexdso.html */ int n,m;cin>>n>>m; int ans=m; vvi g(n+1),g1(n+1); vi din(n+1); vi ta(n+1); for (int i=1;i<=n;i++) cin>>ta[i]; for (int i=1;i<=m;i++) { int u,v;cin>>u>>v; g[u].push_back(v); } for (int i=1;i<=n;i++) { vi tc; for (auto v:g[i]) { if(ta[v]>ta[i]) { tc.push_back(v); } } g1[i]=g[i]; g[i]=tc; } for (int i=1;i<=n;i++) { auto tv=g[i]; for (auto v:tv) { din[v]++; } } vi dp(n+1); vi vis(n+1); vector<map<int,int>> cnt(n+1); auto dfs=[&](auto self,int u)->void { vis[u]=1; // cout<<u<<endl; for (auto v:g[u]) { din[v]--; if(vis[v]==0) self(self,v); cnt[u][ta[v]-ta[u]]=(cnt[u][ta[v]-ta[u]]+cnt[v][ta[u]]+1)%mod; } }; for (int i=1;i<=n;i++) { if(!din[i]&&vis[i]==0) { // cout<<i<<endl; dfs(dfs,i); } } for (int i=1;i<=n;i++) { for (auto v:g1[i]) { ans=(ans+cnt[v][ta[i]])%mod; } // cout<<i<<" "<<ans<<endl; } cout<<ans<<endl;
