比赛 NOIP模拟赛by mzx Day2 评测结果 AAAAAAAAAA
题目名称 森林大礼包 最终得分 100
用户昵称 宋逸群 运行时间 1.503 s
代码语言 C++ 内存使用 20.39 MiB
提交时间 2016-10-20 20:21:00
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 100010
typedef long long ll;
const ll INF=1e9+7;
struct node{ll y,next;}e[MAXN*10];
ll n,len,Link[MAXN],v[MAXN],id[MAXN],q[MAXN*10];
inline ll read()
{
	ll x=0,f=1;  char ch=getchar();
	while(!isdigit(ch))  {if(ch=='-')  f=-1;  ch=getchar();}
	while(isdigit(ch))  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void insert(ll x,ll y)  {e[++len].next=Link[x];Link[x]=len;e[len].y=y;id[y]++;}
void topsort()
{
	ll head=0,tail=0;  v[0]=1;
	for(ll i=0;i<=n;i++)  if(!id[i])  q[++tail]=i;
	while(++head<=tail)
	{
		ll x=q[head];
		for(ll i=Link[x];i;i=e[i].next)
		{
			v[e[i].y]+=v[x];  v[e[i].y]%=INF;
			if(--id[e[i].y]==0)  q[++tail]=e[i].y;
		}
	}
}
int main()
{
	freopen("three_squirrels.in","r",stdin);
	freopen("three_squirrels.out","w",stdout);
	n=read();
	for(ll i=1;i<=n;i++)
	{
		ll T=read();
		while(T--)  {ll x=read();  insert(x,i);}
	}
	topsort();
	printf("%lld\n",v[n]%INF);
	return 0;
}