比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 丁司令 运行时间 1.167 s
代码语言 C++ 内存使用 8.52 MiB
提交时间 2016-10-20 21:45:37
显示代码纯文本
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const int mo=1e9+7;
ll n,x1,y1;
ll head[100025],cnt,f[100005];
struct LU{
	int next,v;
}a[1000050];
ll dfs(ll i)
{
	ll sum=0;
	if(f[i]) return f[i];
	for(int j=head[i];j;j=a[j].next)
	  {
	  f[a[j].v]=dfs(a[j].v)%mo;
	  sum+=f[a[j].v];
	  sum%=mo;
       }
	return sum%mo;
}
int main()
{
	freopen("three_squirrels.in","r",stdin);
	freopen("three_squirrels.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++)
	  {
	  	scanf("%d",&x1);
	  	for(int j=1;j<=x1;j++)
	  	  {
			scanf("%d",&y1);
		    cnt++;
		    a[cnt].v=y1;
		    a[cnt].next=head[i];
		    head[i]=cnt;
		  }
	  }
	f[0]=1;
	for(int i=1;i<=n;i++)
	  f[i]=dfs(i);
	cout<<f[n]%mo;
	fclose(stdin);
	fclose(stdout);
	return 0;
}