XA-Game 题解

· · 题解

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

可以发现一些性质：

我们现在可以猜想如果每次 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 赢：

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

如果不满足第一个条件，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;
}