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

· · 题解

既然 A 的操作是变成两个数的异或和，那么我们不妨从整个序列的异或和入手，因为 A 的操作不会改变整个序列的异或和，而最后 A 获胜的充要条件是异或和为 1。

于是我们来考虑 B 的操作对于异或和的影响。如果选择的两个数是 01,10,11，则异或和都会改变；如果是 00 则异或和不变。

那么 B 的目标是让最终异或和为 0。而只有 B 能操控异或和，那么 B 优势很大啊！进一步地，只要让 B 拿到一个有 00 的序列，B 就必胜。

为什么呢？我们先假设 B 每一步序列异或和都会改变，那如果 B 一直不选 00，最终异或和会是 1 的话，B 这次把 00 选了就可以拿下。否则这次需要选 00 之外的东西才能必胜（保持最终异或和是 0），万一没有呢？没有更好啊，整个序列都是 0，已经必胜了。

所以 A 获胜的第一个条件就呼之欲出了：初始序列中至多有一个 00（A 可以先手操作消灭它）。

消灭之后，B 的所有操作都会改变异或和，A 的所有操作都不改变异或和。问题就简单了，只需要保证 1 的数量加上 B 的操作次数是奇数就可以了。

也就是 A 获胜的第二个条件：cnt_1+\lfloor\frac{n-1}{2}\rfloor\bmod 2=1（cnt_1 为 1 的数量）。

于是可以开始 dp，记录三个东西：有没有出现过 00、上一位是啥、当前的 cnt_1\bmod 2。转移很好做。

考虑把这个第二维只有 8 的线性 dp 矩阵快速幂优化掉，似乎就做完了？

实际上跑得很慢，但是注意到转移矩阵都是固定的，只是幂次不同。可以预处理光速幂优化，具体见代码。这样可以去掉一个 \operatorname{log}n，求的时候矩阵乘法也从 V^3 变成 V^2，可以通过。

#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;
}