Codeforces 273E. Dima and Game

题意：

Dima和Anya在玩游戏，规则是这样的：一张纸上有有序的$n$对数$(l_i, r_i)(1 \le l_i \lt r_i \le p)$，然后它们轮流进行操作：选一对数$(l_i, r_i)$满足$r_i - l_i \gt 2$，然后把它变成$(l_i + \lfloor \frac{r_i - l_i} 3 \rfloor, l_i + 2 \cdot \lfloor \frac{r_i - l_i} 3 \rfloor)$或$(l_i, r_i - \lfloor \frac{r_i - l_i} 3 \rfloor)$。不能移动的人就输了。给出$n$和$p$，求出能让先手获胜的方案数。

题解：

首先打个表找找规律，发现sg值一大段一大段都是一样的，所有我们可以直接把一整段的sg值求出来，然后dp就很简单了吧。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <utility>
using namespace std;

const int mod = 1000000007, inv2 = 500000004;
int n, p;
long long s[3], f[1010][4];
struct th
{
    int l, r, c;
    th(int l, int r, int c) : l(l), r(r), c(c) {}
    th(int r) : r(r) {}
};
bool operator<(th x, th y)
{
    return x.r < y.r;
}
vector<th> t;

int mex(int x, int y)
{
    static bool hh[3];
    hh[0] = hh[1] = hh[2] = 0;
    hh[x] = hh[y] = 1;
    for (int i = 0; i < 3; i++)
        if (!hh[i]) return i;
}
long long get(long long x, long long y)
{
    return (x + y) % mod * (y - x + 1) % mod * inv2 % mod;
}
int main()
{
    scanf("%d%d", &n, &p);
    if (p <= 2)
    {
        puts("0");
        return 0;
    }
    t.emplace_back(1, 2, 0);
    t.emplace_back(3, 3, 1);
    t.emplace_back(4, 4, 2);
    t.emplace_back(5, 6, 1);
    // int cnt = 0;
    while (t.back().r < p)
    {
        int a1 = (t.back().r + 1) / 3;
        auto it1 = lower_bound(t.begin(), t.end(), a1);
        int a2 = t.back().r + 1 - a1;
        auto it2 = lower_bound(t.begin(), t.end(), a2);
        int b1 = it1->r, b2 = it2->r;
        int c = mex(it1->c, it2->c), r;
        if (b1 * 2 + 2 > b2)
        {
            b1 = b2 / 2;
            r = b1 + b2;
        }
        else
            r = b1 * 3 + 2;
        if (c == t.back().c) t.back().r = r;
        else t.emplace_back(t.back().r + 1, r, c);
        // cnt++;
    }/*
    for (th x : t)
        printf("%d %d %d\n", x.l, x.r, x.c);*/
    // printf("%d\n", cnt);
    for (const th &x : t)
    {
        if (x.l >= p) break;
        (s[x.c] += get(max(1, p - x.r), p - x.l)) %= mod;
    }
    // printf("%lld %lld %lld\n", s[0], s[1], s[2]);
    f[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= 3; j++)
            for (int k = 0; k <= 3; k++)
                if ((j ^ k) <= 2)
                    (f[i][j] += (f[i - 1][k] * s[j ^ k]) % mod) %= mod;
        // printf("%lld %lld %lld %lld\n", f[i][0], f[i][1], f[i][2], f[i][3]);
    }
    printf("%lld\n", (f[n][1] + f[n][2] + f[n][3]) % mod);
}