自动搬运

查看原文

来自洛谷，原作者为

	larsr loser

搬运于2025-08-24 23:06:27，当前版本为作者最后更新于2024-08-18 19:07:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

现在我们观察一下 $\operatorname{xor}$ 和 $\operatorname{and}$ 的操作效果。

• $\operatorname{xor}$ ：
• • $0\ 0\rarr 0$
• • $0\ 1\rarr 1$
• • $1\ 0\rarr 1$
• • $1\ 1\rarr 0$
• $\operatorname{and}$ ：
• • $0\ 0\rarr 0$
• • $0\ 1\rarr 0$
• • $1\ 0\rarr 0$
• • $1\ 1\rarr 1$

可以发现一些性质：

• $\operatorname{xor}$ 操作完 $1$ 的数量只会减少 $0$ 和 $2$，也就是说 $1$ 的数量的奇偶性不变。
• 除了 $[0,0]$，$\operatorname{and}$ 操作完都会使 $1$ 的数量减少 $1$，也就是说 $1$ 的数量的奇偶性会变。

我们现在可以猜想如果每次 dalao 操作序列时都没有 $[0,0]$ 的部分，那么 dalao 的操作就变得可控了。想让这种情况成立，那么 LLL 每次操作时序列必须最多有一处连续的 $0$。如果初始时这种情况成立，那么每次这种情况都成立，因为 dalao 每次只能减少一个 $1$，最多能让 $[0,1,0]$ 变成 $[0,0]$，也就是说最多产生一处连续的 $0$。

可以知道 dalao 会操作 $\lfloor \frac{n-1}{2}\rfloor$ 次，那么初始时的 $1$ 的奇偶性要与 $\lfloor \frac{n-1}{2}\rfloor$ 不同。那么符合以下性质的 01 序列必然可以 LLL 赢：

• $1$ 的数量的奇偶性和 $\lfloor \frac{n-1}{2}\rfloor$ 不同。
• 最多有一处连续的 $0$。

证明完以上的序列成立，我们还要证明不满足以上条件的序列不成立。

如果不满足第一个条件，dalao 可以每次都减少一个 $1$。而只有序列是全 $0$ 时，dalao 才不能减少一个 $1$，但此时 LLL 已经必输了。

如果满足第一个条件不满足第二个条件，dalao 可以选择一个有一处连续的 $0$ 的时刻，选择这个连续的 $0$，其他时刻都减少一个 $1$。而只有序列是全 $0$ 时，dalao 才不能减少一个 $1$，但此时 LLL 已经必输了。

证明完以上，问题就变简单了。可以设状态 $f_{i,0/1,0/1,0/1}$ 代表有 $i$ 个数，最后一个数为 $0/1$，$1$ 的数量的奇偶性为 $0/1$，出现了 $0/1$ 处连续的 $0$，的 01 序列的数量。然后可以 $O(n)$ 递推出来，如果初始时预处理，那么可以获得 $65$ 分。

很明显可以用矩阵乘法加速，复杂度 $O((t+\sum m)V^3\log n)$，$V$ 代表矩阵边长，如果再带上线性算法可以获得 $80$ 分。

然后可以利用光速幂的思想优化到 $O((t+\sum m)V^2)$（不包括预处理），然后就可以 AC 了。

#include<cstdio>
#include<cstring>
#define P 100000
#define N 500010
#define mod 1000000007
#define ll long long
#define zy(a,b,c) ((a)*4+(b)*2+(c))
using namespace std;
ll n, m, a[N], v[N];
struct mat
{
	ll a[8][8];
	mat operator *(mat x)
	{
		mat ans;
		memset(ans.a, 0, sizeof ans.a);
		for(int i = 0; i < 8; i++)
			for(int j = 0; j < 8; j++)
				for(int k = 0; k < 8; k++)
					ans[i][k] = (ans[i][k] + a[i][j] * x[j][k]) % mod;
		return ans;
	}
	ll* operator [](int x)
	{
		return a[x];
	}
};
mat a0, a1, ap, mul[P+10][3], danw;
//last number, sum of number 1 mod 2, number of [0,0]
void init()
{
	for(int i = 0; i < 8; i++)danw[i][i] = 1;
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < 2; j++)
			for(int k = 0; k < 2; k++)
			{
				if(i || !k)
				{
					a0[zy(i,j,k)][zy(0,j,k|(!i))] = 1;
					ap[zy(i,j,k)][zy(0,j,k|(!i))] = 1;
				}
				a1[zy(i,j,k)][zy(1,j^1,k)] = 1;
				ap[zy(i,j,k)][zy(1,j^1,k)] = 1;
			}
	for(int i = 0; i < 3; i++)
	{
		mul[0][i] = danw;
		mat x;
		if(!i)x = ap;
		else x = mul[P][i - 1];
		for(int j = 1; j <= P; j++) mul[j][i] = mul[j - 1][i] * x;
	}
}
ll f[8];
void pus(mat x)
{
	ll tmp[8];
	memset(tmp, 0, sizeof tmp);
	for(int i = 0; i < 8; i++)
		for(int j = 0; j < 8; j++)
			tmp[j] = (tmp[j] + f[i] * x[i][j]) % mod;
	memcpy(f, tmp, sizeof f);
}
void appus(ll x)
{
	if(x % P != 0)pus(mul[x % P][0]);
	if((x / P) % P != 0)pus(mul[(x / P) % P][1]);
	if(x / P / P != 0)pus(mul[x / P / P][2]);
}
ll read()
{
	ll x = 0;
	char c = getchar();
	while(c < '0' || c > '9')c = getchar();
	while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
	return x;
}
void slove()
{
	n = read();
	m = read();
	memset(f, 0, sizeof f);
	f[zy(1,1,0)] = 1;
	ll ss = 1;
	for(int i = 1; i <= m; i++)
	{
		ss = ss * 2 % mod;
		a[i] = read();
		v[i] = read();
		appus(a[i] - a[i - 1] - 1);
		if(v[i] == 0)pus(a0);
		else pus(a1);
	}
	appus(n - a[m]);
	int w = (n - 1) / 2 % 2;
	ll ans = 0;
	for(int i = 0; i < 2; i++)
		for(int j = 0; j < 2; j++)
			ans = (ans + f[zy(i,w,j)]) % mod;
	printf("%lld\n", ans * ss % mod);
}
int main()
{
	init();
	int t;
	t = read();
	while(t--)slove();
	return 0;
}