题意分析

我们需要解决的问题是：在乌托邦镇有一群面包师，他们每月举行一次庆祝活动。在每次庆祝活动中，会根据面包师房子上的粉笔标记数量（奇数为获奖者）选出获奖者。获奖者会在他们最喜欢的面包师的房子上添加粉笔标记。我们需要计算第 t 次庆祝活动的获奖者数量。

解题思路

1.建模问题： 每个面包师的状态可以用其房子上的粉笔标记数量的奇偶性来表示（奇数为 1，偶数为 0）。 每次庆祝活动，获奖者会在他们最喜欢的面包师的房子上添加一个粉笔标记。这相当于对最喜欢的面包师的奇偶性进行异或操作（因为加 1 相当于奇偶性翻转）。 因此，我们可以将问题建模为一个状态转移问题，其中状态是一个向量，表示每个面包师的奇偶性，转移是一个矩阵，表示每个面包师对其他面包师的影响。

2.矩阵快速幂： 由于 t 可以达到 1,000,000,000，我们需要使用矩阵快速幂来高效计算 t 次操作后的状态。 定义一个转移矩阵 A，其中 $A[i][j]$表示面包师 i 是否在面包师 j 的最喜欢列表中（是则为 1，否则为 0）。 每次操作相当于将状态向量 v 乘以转移矩阵 A，并对结果取模 2（因为只关心奇偶性）。 因此，t 次操作后的状态可以表示为 $v \cdot A^{t-1}$。

3.初始状态和结果计算： 初始状态向量 v 是每个面包师的初始粉笔标记数量的奇偶性。 计算 $v \cdot A^{t-1}$后的向量，统计其中为 1 的数量，即为第 t 次庆祝活动的获奖者数量。

代码实现

#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <cstdio>
#define MAX_N 105
using namespace std;

int n, t, indexnum;

struct matrix
{
	int m[MAX_N][MAX_N];
};

int ia[MAX_N], res[MAX_N];
matrix rel;

map<string, int> mapper;

//计算a * b并将结果放在c中 a为s1 * s2矩阵，b为s2 * s3矩阵
matrix mult(const matrix &a, const matrix &b)
{
	matrix res;
	memset(res.m, 0, sizeof(res.m));
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			for(int k = 0; k < n; k++)
				res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % 2;
	return res;
}

//计算a的p次方并将结果放在a中
matrix pow(matrix a, int p)
{
	matrix temp;
	int i;
	memset(temp.m, 0, sizeof(temp.m));
	for(i = 0; i < n; i++) temp.m[i][i] = 1;
	while(p > 0)
	{
		if(p & 1) temp = mult(temp, a);
		a = mult(a, a);    
		p>>=1;
	}
	return temp;
}

int solve()
{
	int i, j, k;
	mapper.clear();
	scanf("%d%d", &n, &t);
	memset(rel.m, 0, sizeof(rel.m));
	memset(ia, 0, sizeof(ia));
	indexnum = 0;
	string name;
	map<string, int>::iterator iter;
	int index1 = 0, index2 = 0;
	for(i = 0; i < n; i++)
	{
		cin>>name;
		if((iter = mapper.find(name)) == mapper.end())
			mapper[name] = index1 = indexnum++;
		else index1 = iter->second;
		int relnum = 0;
		cin>>ia[index1]>>relnum;
		ia[index1] = ia[index1] % 2;
		for(j = 0; j < relnum; j++)
		{
			cin>>name;
			if((iter = mapper.find(name)) == mapper.end())
				mapper[name] = index2 = indexnum++;
			else index2 = iter->second;
			rel.m[index1][index2] = (rel.m[index1][index2] + 1) % 2;
		}
		rel.m[index1][index1] = (rel.m[index1][index1] + 1) % 2;    
	}
	rel = pow(rel, t - 1);
	memset(res, 0, sizeof(res));
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
			res[i] = (res[i] + ia[j] * rel.m[j][i]) % 2; 
	int total = 0;
	//统计winner的个数
	for(i = 0; i < n; i++)
		if(res[i] == 1) total++;
	return total;
}

int main()
{
	int caseN;
	cin>>caseN;
	while(caseN--)
		cout<<solve()<<endl;
	return 0;
}