专栏文章

题解：P11326 【MX-S7-T4】「SMOI-R2」XA-Game

MMPLN
P11326题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min3ukn9
此快照首次捕获于
2025/12/01 20:07
3 个月前
此快照最后确认于
2025/12/01 20:07
3 个月前
查看原文
既然 A 的操作是变成两个数的异或和，那么我们不妨从整个序列的异或和入手，因为 A 的操作不会改变整个序列的异或和，而最后 A 获胜的充要条件是异或和为 11。
于是我们来考虑 B 的操作对于异或和的影响。如果选择的两个数是 01,10,1101,10,11，则异或和都会改变；如果是 0000 则异或和不变。
那么 B 的目标是让最终异或和为 00。而只有 B 能操控异或和，那么 B 优势很大啊！进一步地，只要让 B 拿到一个有 0000 的序列，B 就必胜。
为什么呢？我们先假设 B 每一步序列异或和都会改变，那如果 B 一直不选 0000，最终异或和会是 11 的话，B 这次把 0000 选了就可以拿下。否则这次需要选 0000 之外的东西才能必胜（保持最终异或和是 00），万一没有呢？没有更好啊，整个序列都是 00，已经必胜了。
所以 A 获胜的第一个条件就呼之欲出了：初始序列中至多有一个 0000（A 可以先手操作消灭它）。
消灭之后，B 的所有操作都会改变异或和，A 的所有操作都不改变异或和。问题就简单了，只需要保证 11 的数量加上 B 的操作次数是奇数就可以了。
也就是 A 获胜的第二个条件：cnt1+⌊n−12⌋ mod 2=1cnt_1+\lfloor\frac{n-1}{2}\rfloor\bmod 2=1（cnt1cnt_1 为 11 的数量）。
于是可以开始 dp，记录三个东西：有没有出现过 0000、上一位是啥、当前的 cnt1 mod 2cnt_1\bmod 2。转移很好做。
考虑把这个第二维只有 88 的线性 dp 矩阵快速幂优化掉，似乎就做完了？
实际上跑得很慢，但是注意到转移矩阵都是固定的，只是幂次不同。可以预处理光速幂优化，具体见代码。这样可以去掉一个 log⁡n\operatorname{log}n，求的时候矩阵乘法也从 V3V^3 变成 V2V^2，可以通过。
CPP
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MOD=1000000007,B=1e5;
struct matrix{
	int n,m,a[9][9];
	matrix(int _n=0,int _m=0){n=_n,m=_m;memset(a,0,sizeof(a));}
	void init(int op){
		// 00ed / lastd / xorsum
		n=m=8,memset(a,0,sizeof(a));
		for(int i=0;i<8;i++)for(int d=0;d<=1;d++){
			if(!(op&(1<<d))) continue;
			if((i&4)&&!(i&2)&&!d) continue;
			int ni=0;
			ni|=(i&1^d),ni|=2*d;
			if((i&4)||(!(i&2)&&d==0)) ni|=4;
			a[i][ni]=op==3?1:2;
		}
	}
	matrix operator*(const matrix &x)const{
		matrix res(n,x.m);
		for(int i=0;i<n;i++)for(int j=0;j<x.m;j++)for(int k=0;k<m;k++)
			res.a[i][j]=(res.a[i][j]+a[i][k]*x.a[k][j])%MOD;
		return res;
	}
}pre[300010];
matrix mul(matrix a,int k){
	if(!k) return a;
	if(k%100000) a=a*pre[k%100000];
	k/=100000;if(!k) return a;
	if(k%100000) a=a*pre[B+k%100000];
	k/=100000;if(!k) return a;
	if(k%100000) a=a*pre[B+B+k%100000];
	return a;
}
int T,n,m;
signed main(){
	pre[1].init(3);
	for(int i=2;i<=B;i++) pre[i]=pre[i-1]*pre[1];
	pre[B+1]=pre[B];
	for(int i=2;i<=B;i++) pre[i+B]=pre[i+B-1]*pre[B+1];
	pre[B+B+1]=pre[B+B];
	for(int i=2;i<=B;i++) pre[i+B+B]=pre[i+B+B-1]*pre[B+B+1];
	cin>>T;
	while(T--){
		cin>>n>>m;
		matrix res(1,8); res.a[0][2]=1;
		int lst=0;
		for(int i=1,x,v;i<=m;i++){
			cin>>x>>v;
			res=mul(res,x-lst-1);
			matrix tmp; tmp.init(1<<v);
			res=res*tmp;
			lst=x;
		}
		res=mul(res,n-lst);
		int tarxor=((n-1)/2)&1^1,ans=0;
		for(int i=0;i<8;i++)if((i&1)==tarxor)
			ans=(ans+res.a[0][i])%MOD;
		cout<<ans<<endl;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...