洛谷P7606 [THUPC2021] 混乱邪恶题解

题目链接：P7606 [THUPC2021] 混乱邪恶

题意：

给你一个蜂窝网络，你初始在坐标 \((0,0)\) 。这个网络中每个交叉点共有 \(6\) 个相邻的交叉点

共有两种属性 \(L,R\) （守序值和善良值），初始为 \(0\) ，均在\(\bmod p\) 意义下存在。

现在有 \(n\) 张卡片，第 \(i\) 张使用后可以选择向任意方向（\(6\) 个方向）前进一步。

如果向 \(j\) 方向前进，则会使得 \(L\gets L+l_{i,j},\,R\gets R + r_{i,j}\) （在\(\bmod p\) 意义下）。

问是否有一种方案使得自己最后能够回到 \((0,0)\) 且 \(L=L_0,R=R_0\) 。

输入格式：

第一行两个正整数 \(n,p\)。

接下来 \(n\) 行，每行 \(2\times 6\) 个非负整数 \(l_{i,j},r_{i,j}~(1 \le j \le 6)\)。

最后一行两个非负整数 \(L_0,R_0\)。

输出格式：

如果能，输出一行 Chaotic Evil。

如果不能，输出一行 Not a true problem setter。

数据范围：

保证 \(1 \le n \le 100\)，\(1 \le p \le 100\)。保证其他输入数据在 \(0\) 到 \(p-1\) 之间。

首先把这个蜂窝图摆正，那么就变成了一个多加了斜边的网格图。

设 \(f(i,l,r,x,y)\) 表示考虑前 \(i\) 张牌当前在 \(x,y\) 时能否使得 \(L,R\) 为 \(l,r\) 。

这里需要引入一个模型：随机游走。

一只蜘蛛原本在蛛网中央，现在它开始在网上乱走，步长为 \(1\) 个单位长度

但是最后又回到了原点，假设它一共走了 \(k\) 步，求它期望走到的相对于原点的最远距离为多少？

这个模型给出的答案是 \(\sqrt{n}\) 。

更复杂一些的模型是（~~其实这道题不需要这个模型，仅作介绍~~）

给你一个长度为 \(n\) 的数列 \(a\)，要求从其中随机选取元素。

每个元素只能选一次，一直选完整个数列并且最后的和为 \(0\) 。

如果对于任意 \(1 \le i \le n\) 都有 \(|a_i| \le c\) ，求在整个选取过程中，

已选元素之和 \(S\) 的期望最大值和最小值分别为多少？

答案是 \(-c\sqrt{n} \le \mathrm{E}(S) \le c\sqrt{n}\) 。

不过和这道题的区别在于，我们可以选择怎么走，而不是乱走。

由于 \(x,y \le 100\) 而且我们无从得知可行的走法（除了强行 \(\mathcal{O}(n^3p^2)\) 的dp）。

所以我们可以开摆，把所有的卡牌随机一下，这样就相当于每次在随机瞎走了

由于期望的最远距离是 \(\sqrt{n}\) ，所以我们 \(x,y\) 只需要开到 \(\mathcal{O}(\sqrt{n})\) 即可，实际上开到 \(2\sqrt{n}\) 能保证正确率。

那么剩下的就是简单的 dp 了，然后 \(y\) 这一维可以用 bitset 来做（用 bitset 比 long long 快）。

时间复杂度 \(\mathcal{O}\left(\frac{n^2p^2}{\omega}\right)\)

代码：（常数巨大）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(105))
#define M 51

mt19937 rd(time(0));
int n, p, a[N][M];
bitset<M> f[2][N][N][M];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> p; const int limit = 2 * (sqrt(n) + 1);
    rep(i, 1, n) rep(j, 1, 12) cin >> a[i][j];
    shuffle(a + 1, a + 1 + n, rd);
    static const auto mod = [](int x) { while(x >= p) x -= p; return x; };
    int L, R; cin >> L >> R; f[0][0][0][limit][limit] = true;
    rep(i, 1, n) rep(l, 0, p - 1) rep(r, 0, p - 1) rep(x, 0, limit * 2)
    {
        const int cur = i & 1, pre = cur ^ 1;
        auto &now = f[cur][l][r][x]; now.reset();
        now |= f[pre][mod(l - a[i][1] + p)][mod(r - a[i][2] + p)][x] << 1;
        now |= f[pre][mod(l - a[i][7] + p)][mod(r - a[i][8] + p)][x] >> 1;
        if(x != xEND)
        {
            now |= f[pre][mod(l - a[i][3] + p)][mod(r - a[i][4] + p)][x + 1];
            now |= f[pre][mod(l - a[i][5] + p)][mod(r - a[i][6] + p)][x + 1] >> 1;
        }
        if(x != 0)
        {
            now |= f[pre][mod(l - a[i][9] + p)][mod(r - a[i][10] + p)][x - 1];
            now |= f[pre][mod(l - a[i][11] + p)][mod(r - a[i][12] + p)][x - 1] << 1;
        }
    }
    if(f[n & 1][L][R][limit][limit]) cout << "Chaotic Evil\n";
    else cout << "Not a true problem setter\n";
    return 0;
}