P7606 [THUPC2021] 混乱邪恶

, ,

Description

https://www.luogu.com.cn/problem/P7606

Solution

感觉非常背包啊！于是就开五维分别记录第几个，第一维的模 $p$ 的值，第二位模 $p$ 的值，第一维在坐标的位置，第二维在坐标的位置。观察答案只判断是否，所以可以 bitset 优化一下。

但是感觉还是过不去啊。

看到标签随机化，然后发现输入的那个东西跟顺序没关系，随机交换一下，把第四维第五维范围缩小一下就过了。

具体的正确率在于，第四维和第五维相当于每次走一步的游走，而有经典结论 $1,-1$ 随机构成序列的期望最大前缀和长度是 $O(\sqrt n)$ 级别的，对应到这道题目上，随机游走的最大范围是期望 $O(\sqrt n)$ 的。

我们离随机游走只差随机，随机一下就好了。具体分析可以看官方题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 105
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
const int base=25;
bitset<55>f[2][105][105][105];
int fx[6]={1,0,-1,-1,0,1};
int fy[6]={0,1,1,0,-1,-1};
int a[maxn][6][2],s,t,n,p;
int id[maxn];
mt19937 rnd(time(0));
signed main(void){
	int i,j,k,l,o,q;
	read(n);read(p);
	for (i=1;i<=n;i++) {
		for (j=0;j<6;j++) read(a[i][j][0]),read(a[i][j][1]);
		id[i]=i;
	}
	shuffle(id+1,id+1+n,rnd);
	for (i=1;i<=n;i++) swap(a[id[i]],a[i]);
	read(s);read(t);
	f[0][0][0][base][base]=1;
	const int block=25;
	for (i=1;i<=n;i++) {
		int now=i&1,pre=now^1;
		for (j=0;j<p;j++) {
			for (k=0;k<p;k++) {
				int r=min(min(i,n-i),block);
				for (l=base-r;l<=base+r;l++)
					f[now][j][k][l].reset();
				for (o=0;o<6;o++) {
					int tmpx=(j-a[i][o][0]+p)%p,tmpy=(k-a[i][o][1]+p)%p;
					int r=min(min(i,n-i),block);
					for (l=base-r;l<=base+r;l++) {
						if (fy[o]==0) f[now][j][k][l]|=f[pre][tmpx][tmpy][l-fx[o]];
						else if (fy[o]==1) f[now][j][k][l]|=f[pre][tmpx][tmpy][l-fx[o]]>>1;
						else f[now][j][k][l]|=f[pre][tmpx][tmpy][l-fx[o]]<<1;
					}
				}
			}
		}
	}
	puts(f[n&1][s][t][base][base]?"Chaotic Evil":"Not a true problem setter");
	return 0;
}