前言

今天做题的时候，觉得自己的线性基很假。。
于是重新学了一下。。

资料

线性基

题解

这题的话，考虑到如果质数个数是偶数，就是完全平方数
一个DP比较简单。。
但是我们考虑线性基
在这个序列里面，我们选择的子集，如果为0，那么数量是$2^{cnt}$
cnt是不在基里面的个数
因为基里面的数都是线性无关的

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=200005;
int n,m;
struct qq
{int x,y,last;
}e[N];int num,last[N];
void init (int x,int y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
bool f[2][N];
int d[N];
int xx;
int sta[N];
bool tf=false;
bool vis[N];
void dfs (int x,int y,int now)
{if (d[y]==0&&x==1){printf("Win\n");for (int u=1;u<=now;u++) printf("%d ",sta[u]);exit(0);}tf|=vis[y];if (f[x][y])    return ;vis[y]=true;f[x][y]=true;for (int u=last[y];u!=-1;u=e[u].last){int yy=e[u].y;sta[now+1]=yy;dfs(x^1,yy,now+1);}vis[y]=false;
}
int main()
{memset(vis,false,sizeof(vis));num=0;memset(last,-1,sizeof(last));scanf("%d%d",&n,&m);for (int u=1;u<=n;u++){scanf("%d",&d[u]);for (int i=1;i<=d[u];i++){int y;scanf("%d",&y);init(u,y);}}scanf("%d",&xx);sta[1]=xx;dfs(0,xx,1);if (tf) printf("Draw");else printf("Lose");return 0;
}