比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 丁司令 运行时间 1.167 s
代码语言 C++ 内存使用 8.52 MiB
提交时间 2016-10-20 21:45:37
显示代码纯文本
  1. #include<iostream>
  2. #include<cstdio>
  3. #define ll long long
  4. using namespace std;
  5. const int mo=1e9+7;
  6. ll n,x1,y1;
  7. ll head[100025],cnt,f[100005];
  8. struct LU{
  9. int next,v;
  10. }a[1000050];
  11. ll dfs(ll i)
  12. {
  13. ll sum=0;
  14. if(f[i]) return f[i];
  15. for(int j=head[i];j;j=a[j].next)
  16. {
  17. f[a[j].v]=dfs(a[j].v)%mo;
  18. sum+=f[a[j].v];
  19. sum%=mo;
  20. }
  21. return sum%mo;
  22. }
  23. int main()
  24. {
  25. freopen("three_squirrels.in","r",stdin);
  26. freopen("three_squirrels.out","w",stdout);
  27. cin>>n;
  28. for(int i=1;i<=n;i++)
  29. {
  30. scanf("%d",&x1);
  31. for(int j=1;j<=x1;j++)
  32. {
  33. scanf("%d",&y1);
  34. cnt++;
  35. a[cnt].v=y1;
  36. a[cnt].next=head[i];
  37. head[i]=cnt;
  38. }
  39. }
  40. f[0]=1;
  41. for(int i=1;i<=n;i++)
  42. f[i]=dfs(i);
  43. cout<<f[n]%mo;
  44. fclose(stdin);
  45. fclose(stdout);
  46. return 0;
  47. }