题目描述：（暂不提供）
这道题考场就想出来了。
很明显这是一道 D A G DAG DAG上跑 D P DP DP的题目，想到拓扑。
然后突然就脑抽了一下，忘记了拓扑。
不过还好，也就是推了一分钟就把拓扑和 D P DP DP推出来了。
这道题主要不是考你思路，主要是看你如何处理那些稀奇古怪的名字。 考场 H a s h Hash Hash选了 998244353 998244353 998244353，然后有一个点被卡了。 以为自己 T 2 T2 T2要垫底了，结果没想到写双哈希的人都被卡了，自己只被卡了一个点，竟然 T 2 T2 T2单题第一。
考后请教 G S M GSM GSM换了双哈希然后就过了。
%:pragma GCC optimize(2) %:pragma GCC optimize("Ofast") %:pragma GCC optimize("inline") #include <cstdio> #include <cstring> #include <algorithm> #include <map> using namespace std; typedef long long ll; const int N = 500010; const int P = 131; const int mo = 1000000007; const int mod = 998244353; const int Mod = 1000000007; map<pair<int, int>, int> vis; struct Edge{ int to,nxt; } g[N << 1]; int last[N],cnt = 0,len; int n,tot = 0,r,stk[N],st[N],l; ll ret = 0,f[N],d[N],ans,bz[N],ret1 = 0; char s[80]; void add(int u,int v) { g[++cnt] = (Edge){ v,last[u] }, last[u] = cnt; } int main() { freopen("chain.in","r",stdin); freopen("chain.out","w",stdout); scanf("%d",&n); for(int i = 1,x,y;i <= n; ++ i) { pair<int, int> tmp = make_pair(0,0); scanf(" %s",s + 1); len = strlen(s + 1); ret = 0, ret1 = 0; for(int j = 1;j <= len; ++ j) if(s[j] >= 'A' && s[j] <= 'Z') { ret = (1ll * ret * P % mod + (s[j] - 'A' + 1)) % mod, ret1 = (1ll * ret1 * P % mo + (s[j] - 'A' + 1)) % mo; } else { ret = (1ll * ret * P % mod + (s[j] - 'a' + 27)) % mod, ret1 = (1ll * ret1 * P % mo + (s[j] - 'a' + 27)) % mo; } tmp = make_pair((int)ret,(int)ret1); if(!vis[tmp]) vis[tmp] = x = ++tot; else x = vis[tmp]; scanf(" %s",s + 1); len = strlen(s + 1); ret = 0, ret1 = 0; for(int j = 1;j <= len; ++ j) if(s[j] >= 'A' && s[j] <= 'Z') { ret = (1ll * ret * P % mod + (s[j] - 'A' + 1)) % mod, ret1 = (1ll * ret1 * P % mo + (s[j] - 'A' + 1)) % mo; } else { ret = (1ll * ret * P % mod + (s[j] - 'a' + 27)) % mod, ret1 = (1ll * ret1 * P % mo + (s[j] - 'a' + 27)) % mo; } tmp = make_pair((int)ret,(int)ret1); if(!vis[tmp]) vis[tmp] = y = ++tot; else y = vis[tmp]; if(x == y) continue; add(x,y); ++d[y]; bz[x] = 1; } ret = 0; l = 1; for(int i = 1;i <= tot; ++ i) if(!d[i]) stk[++r] = i,f[i] = 1,ret = (ret + f[i]) % Mod; ans = ret; ret = 0; for(;l <= r; ++l) for(int i = last[stk[l]];i;i = g[i].nxt) { --d[g[i].to], f[g[i].to] = (f[g[i].to] + f[stk[l]]) % Mod; if(!d[g[i].to]) stk[++r] = g[i].to; if(!bz[g[i].to] && !d[g[i].to]) ret = (ret + f[g[i].to]) % Mod; } if(ret) ans = ret; printf("%lld",ans); fclose(stdin); fclose(stdout); return 0; }