洛谷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;
}