「SMOI-R2」XA-Game 题解
A6n6d6y6
·
·
题解
题意
Alice 和 Bob 在一个 01 序列上玩游戏，Alice 先手。
Alice 每次操作选择相邻两数，将它们合并为它们的异或值。
Bob 每次操作选择相邻两数，将它们合并为它们的与值。
求一共有多少 01 序列满足 Alice 必胜。
其中有 m 组限制形如序列的 a_i 项必为 v_i。（还是算两个不同的序列）。
## 思路
### 题意转化
不难发现，如果有超过**两组**连续的两个 $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;
}
```