自动搬运

查看原文

来自洛谷，原作者为

	SuperJvRuo **

搬运于2025-08-24 22:04:13，当前版本为作者最后更新于2018-10-30 20:22:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

成功拿下此题首杀！NOIP提高组水平的选手们，只要认真读题，就可以做出来。

• 没有机器人又被指控又被保护
• 没有机器人被指控或保护一次以上
• 如果有一个编号为$A$机器人指控或保护编号为$B$的机器人，那么我们保证$A<B$。

这三条限定为什么会使题目更简单呢？

因为它保证了这个图是树形图的集合。我们就可以把这道题当做树形DP来做。

先对每个树形图单独做DP。对于每个树形图中的每个节点，有两种转移：

对于一条“指控”边，狼人儿子可以转移到平民父亲，平民儿子可以转移到狼人或平民父亲；

对于一条“保护”边，平民儿子可以转移到平民父亲，狼人儿子可以转移到狼人或平民父亲。

最后对所有树形图做DP，统计答案，具体的转移方程见代码。

f数组如果不滚动的话，像我这样开得大一点，大概是$205\times205\times2\times205\times8\div2^{20}=131MB$，似乎还是滚动一下比较好。

#include<cstdio>
#include<vector>
#define LL long long
#define MOD 1000000007

struct Edge
{
	int to,next,eff;
    //eff==1表示指控，eff==2表示保护
}edge[205];
int head[205],cnt;

void Add_edge(int u,int v,int opt)
{
	edge[++cnt]=(Edge){v,head[u],opt};
	head[u]=cnt;
}

std::vector<int> root;

LL f[205][2][2][205];
//f[i][j(滚动)][0/1][j]:以i为根的子树，算到第j个儿子，i是/不是狼人，子树中有j个狼人的方案数 
int size[205],son[205];
int indeg[205],outdeg[205];
//入度为0的点一定是一个树形图的根

//求出子树大小、每个节点的儿子数量
void dfs(int u)
{
	size[u]=1;
	for(int i=head[u];i;i=edge[i].next)
	{
		int v=edge[i].to;
		++son[u];
		dfs(v);
		size[u]+=size[v];
	}
}

void calc(int u)
{
	f[u][0][1][1]=f[u][0][0][0]=1;
	for(int i=head[u],num=1;i;i=edge[i].next,num^=1)
	{
		int v=edge[i].to;
		calc(v);
		for(int j=0;j<=size[u];++j)
		{
			f[u][num][0][j]=f[u][num][1][j]=0;
			for(int k=0;k<=size[v];++k)
			{
				if(j>=k)
				{
                	//平民父亲可以由狼人或平民转移
					f[u][num][0][j]+=(f[u][num^1][0][j-k])*(f[v][son[v]&1][0][k]+f[v][son[v]&1][1][k]);
					if(edge[i].eff==1)
					{//狼人一定指控平民
						f[u][num][1][j]+=(f[u][num^1][1][j-k])*(f[v][son[v]&1][0][k]);
					}
					else
					{//狼人一定保护狼人
						f[u][num][1][j]+=(f[u][num^1][1][j-k])*(f[v][son[v]&1][1][k]);
					}
					f[u][num][0][j]%=MOD;
					f[u][num][1][j]%=MOD;
				}
			}
		}
	}
}

LL res[205][205];
//前i个树形图，含j个狼人的方案数

void solve(int n,int w)
{
	for(int i=1;i<=n;++i)
	{
		if(!indeg[i])
		{
			root.push_back(i);
		}
	}
	res[0][0]=1;
    //dp起点，0个狼人的方案数为1
	for(int i=0;i<(int)root.size();++i)
	{
		dfs(root[i]);
		calc(root[i]);
		for(int j=0;j<=size[root[i]];++j)
		{
			for(int k=0;k<=w;++k)
			{
				if(k>=j)
				{
					res[i+1][k]+=res[i][k-j]*(f[root[i]][son[root[i]]&1][1][j]+f[root[i]][son[root[i]]&1][0][j]);
					res[i+1][k]%=MOD;
				}
			}
		}
	}
}

int main()
{
	int n,w,m;
	scanf("%d%d%d",&n,&w,&m);
	char opt[5];
	int u,v;
	for(int i=0;i<m;++i)
	{
		scanf("%s %d %d",opt,&u,&v);
		++indeg[v];
		++outdeg[u];
		Add_edge(u,v,opt[0]=='A'?1:2);
	}
	solve(n,w);
	printf("%lld",res[(int)root.size()][w]);
	return 0;
}