「SMOI-R2」XA-Game 题解

题意

Alice 和 Bob 在一个

01

序列上玩游戏，Alice 先手。

Alice 每次操作选择相邻两数，将它们合并为它们的异或值。

Bob 每次操作选择相邻两数，将它们合并为它们的与值。

求一共有多少

01

序列满足 Alice 必胜。

其中有

m

组限制形如序列的

a_i

项必为

v_i

。（还是算两个不同的序列）。

n\le10^{15},\sum m\le 10^5

，多测。

思路

题意转化

不难发现，如果有超过两组连续的两个

0

（可以有公共的

0

），那么 Bob 总可以保留这些零。

例如，Alice 将其中一个

0

异或上

1

，那么相邻的那个

0

总能又把这个

0

变回来。

最后总会剩下这些

0

，也就是形如

0\cdots0

，那么 Bob 必定赢，不论最开始的先后手。

否则，最后会变成

10

或

01

的情况，此时的先手必胜。

而 Alice 不会改变

1

的数量的奇偶性，只有 Bob 只有对

00

操作不会改变。

由于至多存在一个

00

子串，Alice 可以立即把所有的

00

字串消掉。

那么 Bob 每次都会改变

1

的数量的奇偶性，共

\lfloor\dfrac{n-1}{2}\rfloor

次。

因为最后只剩一个

1

，所以若

1

的数量的奇偶性与 Bob 的总操作次数

\lfloor\dfrac{n-1}{2}\rfloor

相同，最后所有

1

就会被消掉，Alice 就输了。

所以，Alice 能赢当且仅当至多存在一个

00

子串，且

1

的数量的奇偶性与 Bob 的总操作次数

\lfloor\dfrac{n-1}{2}\rfloor

不同。

暴力 DP

然后就可以DP统计满足条件的序列数量了。先不考虑修改，设

f_{i,0/1,0/1,0/1}

表示前

i

位，当前为

0/1

，出现

00

的次数，

1

的次数的奇偶性。

~~转移很简单，就不展开了。~~

转移枚举上一位，结合这一位判断是否出现

0

，和

1

的次数的奇偶性。

可以看一眼代码，初始值

f_{1,1,0,1}=f_{1,0,0,0}=1

。

然后就可以通过一些手模发现

f_{0,1,0,0}=1

和原来的初始化是等价的，然后就可以从

1

开始转移，避免后面的一些分类讨论。

最终答案就是

\sum f_{n,0/1,0/1,\neg k}

，其中

k

为

\lfloor\dfrac{n-1}{2}\rfloor

的奇偶性。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=2e5+10,mod=1e9+7;
int f[maxn][2][2][2];
signed main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;cin>>n;
	f[1][1][0][1]=1;
	f[1][0][0][0]=1;
	for(int i=2;i<=n;i++)
		for(int nw=0;nw<2;nw++)
			for(int s1=0;s1<2;s1++)
				for(int lst=0;lst<2;lst++)
					for(int x=(!nw&&!lst);x<2;x++)
						(f[i][nw][x][s1]+=f[i-1][lst][x-(!nw&&!lst)][s1^nw])%=mod;
	int k=((n-1)/2)%2;
	cout<<(f[n][0][0][!k]+f[n][0][1][!k]+f[n][1][0][!k]+f[n][1][1][!k])%mod;
	return 0;
}

你会发现，这个东西太慢了，不妨先循环展开，就变成了这个样子。

CPP

(f[i][0][0][0]+=f[i-1][1][0][0])%=mod;

(f[i][0][0][1]+=f[i-1][1][0][1])%=mod;

(f[i][0][1][0]+=f[i-1][0][0][0])%=mod;
(f[i][0][1][0]+=f[i-1][1][1][0])%=mod;

(f[i][0][1][1]+=f[i-1][0][0][1])%=mod;
(f[i][0][1][1]+=f[i-1][1][1][1])%=mod;


(f[i][1][0][0]+=f[i-1][1][0][1])%=mod;
(f[i][1][0][0]+=f[i-1][0][0][1])%=mod;

(f[i][1][0][1]+=f[i-1][0][0][0])%=mod;
(f[i][1][0][1]+=f[i-1][1][0][0])%=mod;

(f[i][1][1][0]+=f[i-1][0][1][1])%=mod;
(f[i][1][1][0]+=f[i-1][1][1][1])%=mod;

(f[i][1][1][1]+=f[i-1][0][1][0])%=mod;
(f[i][1][1][1]+=f[i-1][1][1][0])%=mod;

为了方便查看，将后三个状态合为一个，值域

[0,8)

，用二进制的方式存储。

CPP

(f[i][0]+=f[i-1][4])%=mod;
(f[i][1]+=f[i-1][5])%=mod;
(f[i][2]+=f[i-1][0]+f[i-1][6])%=mod;
(f[i][3]+=f[i-1][1]+f[i-1][7])%=mod;

(f[i][4]+=f[i-1][5]+f[i-1][1])%=mod;
(f[i][5]+=f[i-1][0]+f[i-1][4])%=mod;
(f[i][6]+=f[i-1][3]+f[i-1][7])%=mod;
(f[i][7]+=f[i-1][2]+f[i-1][6])%=mod;

其中上半部分是本位为

0

的转移，下半部分是本位为

1

的转移。

那么只需要在对应的

a_i

有限制

v_i

的情况下将另一个部分的

f

值设为

0

，就像：

CPP

if(s[i].v==0)f[4]=f[5]=f[6]=f[7]=0;
if(s[i].v==1)f[0]=f[1]=f[2]=f[3]=0;

然后就有

O(n)

做法了，考虑优化。

矩乘优化

这个转移特别像矩阵乘法的形式，直接套上去即可，转移矩阵自己手推一下，这里不展开叙述。

注意每次相邻的两个

m

值乘上对应的次幂，注意最后的答案要乘上

2^m

（询问的是原始序列数量）。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=5e5+10,mod=1e9+7;
struct vec8{
	int vec[8];
	vec8(){memset(vec,0,sizeof vec);}
	int operator[](int x)const{return vec[x];}
	int& operator[](int x){return vec[x];}
	friend int operator*(const vec8& a,const vec8& b){
		int res=0;
		for(int i=0;i<8;i++)res=(res+a[i]*b[i]%mod)%mod;
		return res;
	}
};
struct mat8{
	vec8 col[8];
	mat8(){}
	vec8 operator[](int x)const{return col[x];}
	vec8& operator[](int x){return col[x];}
	friend vec8 operator*(const vec8&row,const mat8& A){
		vec8 res;
		for(int i=0;i<8;i++)res[i]=row*A[i];
		return res;
	}
	friend mat8 operator*(const mat8&A,const mat8& B){
		mat8 C;
		for(int i=0;i<8;i++)
			for(int j=0;j<8;j++)
				for(int k=0;k<8;k++)
					C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod)%mod;
		return C;
	}
}M;//注意我的实现比较特别，是先列后行
int ksm(int a,int b){
	int c=1;
	while(b){
		if(b&1)c=c*a%mod;
		a=a*a%mod;b>>=1;
	}
	return c;
}
mat8 ksm(mat8 a,int b){
	mat8 c;
	for(int i=0;i<8;i++)c[i][i]=1;
	while(b){
		if(b&1)c=c*a;
		a=a*a;b>>=1;
	}
	return c;
}
struct node{int a,v;}s[maxm];
void solve(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>s[i].a>>s[i].v;
	s[0]={0,-1};s[m+1]={n,-1};
	vec8 f;f[4]=1;
	for(int i=1;i<=m+1;i++){
		f=f*ksm(M,s[i].a-s[i-1].a);
		if(s[i].v==0)f[4]=f[5]=f[6]=f[7]=0;
		if(s[i].v==1)f[0]=f[1]=f[2]=f[3]=0;
	}
	int res=0,k=((n-1)/2)&1;
	for(int i=0;i<8;i++)
		if((i&1)!=k)res=(res+f[i])%mod;
	cout<<res*ksm(2,m)%mod<<'\n';
}
signed main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	M[0][4]=1;M[1][5]=1;
	M[2][0]=1;M[2][6]=1;
	M[3][1]=1;M[3][7]=1;
	M[4][5]=1;M[4][1]=1;
	M[5][0]=1;M[5][4]=1;
	M[6][3]=1;M[6][7]=1;
	M[7][2]=1;M[7][6]=1;
	int t;cin>>t;
	while(t--)solve();
	return 0;
}

然后你就有

60

分了，发现瓶颈在快速幂？这我熟，直接光速幂。

光速幂的大概原理就是，把一个数拆成

s

进制数，其数位只有常数级别。

例如

b=ks+t

，那么

a^b=(a^s)^k\cdot a^t

，其中

k,t\le s,s\ge\sqrt{b}

。

如果分别预处理

a

和

a^s

的

[0,s]

次幂，就可以

O(sw^3)-O(w^3)

求出幂。

本题中由于

b\le10^{15}

，这里取

s=10^5

，那么

b=hs^2+ms+l

，数位最多为

3

。

同理拆开预处理，预处理

a,a^s,a^{s^2}

的

[0,s]

次幂，就可以

O(sw^3)-O(w^3)

求出幂了。

有一个小细节：最后把三个矩阵拼起来的时候直接各自与向量相乘，这样是

O(w^2)

而不是

O(w^3)

的。

总时间复杂度：

O(w^3\sqrt[3]{n}+w^2(\sum m)+q\log m)

，实测可过。

代码

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=5e5+10,mod=1e9+7,maxp=1e5+10,sqp=1e5;
struct vec8{
	int vec[8];
	vec8(){memset(vec,0,sizeof vec);}
	int operator[](int x)const{return vec[x];}
	int& operator[](int x){return vec[x];}
	friend int operator*(const vec8& a,const vec8& b){
		int res=0;
		for(int i=0;i<8;i++)res=(res+a[i]*b[i]%mod)%mod;
		return res;
	}
};
struct mat8{
	vec8 col[8];
	mat8(){}
	vec8 operator[](int x)const{return col[x];}
	vec8& operator[](int x){return col[x];}
	friend vec8 operator*(const vec8&row,const mat8& A){
		vec8 res;
		for(int i=0;i<8;i++)res[i]=row*A[i];
		return res;
	}
	friend mat8 operator*(const mat8&A,const mat8& B){
		mat8 C;
		for(int i=0;i<8;i++)
			for(int k=0;k<8;k++)
				if(A[i][k])for(int j=0;j<8;j++)
					C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod)%mod;
		return C;
	}
}E,M,lw[maxp],md[maxp],hi[maxp];//注意我的实现比较特别，是先列后行
int ksm(int a,int b){
	int c=1;
	while(b){
		if(b&1)c=c*a%mod;
		a=a*a%mod;b>>=1;
	}
	return c;
}
struct node{int a,v;}s[maxm];
void init(){
	for(int i=0;i<8;i++)E[i][i]=1;
	M[0][4]=1;M[1][5]=1;
	M[2][0]=1;M[2][6]=1;
	M[3][1]=1;M[3][7]=1;
	M[4][5]=1;M[4][1]=1;
	M[5][0]=1;M[5][4]=1;
	M[6][3]=1;M[6][7]=1;
	M[7][2]=1;M[7][6]=1;
	lw[0]=md[0]=hi[0]=E;
	for(int i=1;i<=sqp;i++)lw[i]=lw[i-1]*M;
	for(int i=1;i<=sqp;i++)md[i]=md[i-1]*lw[sqp];
	for(int i=1;i<=sqp;i++)hi[i]=hi[i-1]*md[sqp];
}
void transfer(vec8& f,int b){
	int h=b/sqp/sqp%sqp,m=b/sqp%sqp,l=b%sqp;
	f=f*hi[h]*md[m]*lw[l];
}//转移
void solve(){
	int n,m;cin>>n>>m;
	for(int i=1;i<=m;i++)cin>>s[i].a>>s[i].v;
	s[0]={0,-1};s[m+1]={n,-1};
	vec8 f;f[4]=1;
	for(int i=1;i<=m+1;i++){
		transfer(f,s[i].a-s[i-1].a);
		if(s[i].v==0)f[4]=f[5]=f[6]=f[7]=0;
		if(s[i].v==1)f[0]=f[1]=f[2]=f[3]=0;
	}
	int res=0,k=((n-1)/2)&1;
	for(int i=0;i<8;i++)
		if((i&1)!=k)res=(res+f[i])%mod;
	cout<<res*ksm(2,m)%mod<<'\n';
}
signed main(){
//	freopen("game.in","r",stdin);
//	freopen("game.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int t;cin>>t;init();
	while(t--)solve();
	return 0;
}

「SMOI-R2」XA-Game 题解

文章操作

题意

思路

题意转化

暴力 DP

矩乘优化

代码

相关推荐

评论

「SMOI-R2」XA-Game 题解