[CF1290F]Making Shapes

[CF1290F]Making Shapes 题目

传送门 to CF

思路

就在几个小时前，一名学生对着这道题抓耳挠腮，究竟是想不出来任何好点子，于是悲愤而去了。我也早觉得有写一点东西的必要了；这虽然于在座的诸位神犇毫不相干，但在我蒟蒻，却大抵只能如此而已。

由于题目中已规定了是个凸包，又直言平移相同，显然当每个向量的 “用量” 相同时，得到的图形就被判定为相同。于是我们实际上只是求解
{ ∑ c i x i = 0 ∑ c i y i = 0 m ⩾ ∑ c i x i [ x i > 0 ] m ⩾ ∑ c i y i [ y i > 0 ] begin{cases} sum c_ix_i=0\ sum c_iy_i=0\ mgeqslant sum c_ix_i[x_i>0]\ mgeqslant sum c_iy_i[y_i>0] end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​∑ci​xi​=0∑ci​yi​=0m⩾∑ci​xi​[xi​>0]m⩾∑ci​yi​[yi​>0]​

最多 n = 5 n=5 n=5 个变元，用前两个等式换元，则只剩三个变元，有四个不等式约束，还有两个同余约束，问非负整数解的个数。这怎么可能实现？我能想到的最好的方法，就是首先枚举余数（由于 ∣ x ∣ , ∣ y ∣ ⩽ 4 |x|,|y|leqslant 4 ∣x∣,∣y∣⩽4，同余约束的模数较小，先枚举余数来满足之），然后枚举一个变元；剩下两个变元的约束条件相当于半平面交，求整数解就用类欧几里得。我要是打这个，我倒立恰饭。

然而做法究竟是什么呢？这想法也实在是神奇。它基于这样的想法：将比较大小拆分成较长的流程，每一步只需要存储比较少的信息，这样就可以 d p tt dp dp 。必须知道全部才能做的事儿，咋 d p tt dp dp 嘛！

比较大小怎样拆分呢？显然是按照 数位。所以肯定是数位 d p tt dp dp 。我们可以采用二进制下数位，因为这是最优的（函数 x log ⁡ x n xlog_x n xlogx​n 似乎在 x = 2 x=2 x=2 处最小）。

接下来，考虑这 5 5 5 个变元的取值么？那就又成为暴力了。所谓 d p tt dp dp 者，根据关键信息进行分类，然后一起转移。那么显然我们要存下 ∑ c i x i ,    ∑ c i y i sum c_ix_i,;sum c_iy_i ∑ci​xi​,∑ci​yi​ 和那两个不等式是否已经成立。注意我们在做数位 d p tt dp dp，所以已经走过的数位，大多是可以忽略的部分；唯一要存储的往往是进位或退位。二者实际上都差不多；为了方便，我们从低位到高位处理，存储进位。

为了判断大小关系，我们还是要存储 ∑ c i x i [ x i > 0 ] sum c_ix_i[x_i>0] ∑ci​xi​[xi​>0] 的进位。而 ∑ c i x i sum c_ix_i ∑ci​xi​ 的 “进位” 有正有负，麻烦；干脆分别存储 ∑ c i x i [ x i > 0 ] sum c_ix_i[x_i>0] ∑ci​xi​[xi​>0] 和 ∑ c i x i [ x i ⩽ 0 ] sum c_ix_i[x_ileqslant 0] ∑ci​xi​[xi​⩽0]，方便许多。对于 y y y 也是同理。

接下来分析复杂度。由于向量必然需要有正有负，所以最多就是 n − 1 = 4 n-1=4 n−1=4 个 + 4 +4 +4，提供 8 8 8 的进位。多次累积可以达到 V = 16 V=16 V=16 。于是状态数是 log ⁡ m ⋅ V 4 ⋅ 2 2 log mcdot V^4cdot 2^2 logm⋅V4⋅22，转移时枚举哪些 c c c 的当前位是 1 1 1，需 O ( 2 n ) mathcal O(2^n) O(2n)，总复杂度 O ( V 4 2 n log ⁡ m ) = O ( n 4 x 4 2 n log ⁡ m ) mathcal O(V^42^nlog m)=mathcal O(n^4x^42^nlog m) O(V42nlogm)=O(n4x42nlogm) 。看看这美丽的式子，这样的复杂度到哪里去找啊！

精细地计算一下，只有 2 × 1 0 8 2times 10^8 2×108 级别的运算量。也不需要用 “跑不满” 之类的托辞去敷衍了，好耶。

代码

别忘了减掉平凡解 c i = 0 c_i=0 ci​=0，此时面积为零。

#include 
#include 
#include 
#include 
#include 
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long llong;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}

const int MOD = 998244353;
inline void modAddUp(int &x,const int y){
	if((x += y) >= MOD) x -= MOD;
}

const int MAXN = 5;
int x[MAXN], y[MAXN];
int px[1<>i&1){
		if(x[i] > 0) px[S] += x[i];
		else nx[S] -= x[i]; // absolute value
		if(y[i] > 0) py[S] += y[i];
		else ny[S] -= y[i]; // absolute value
	}
	*******dp = 1; // THIS FEELS SO GOOOOOOD
	for0(i,LOGM) for0(apx,MAXV) for0(anx,MAXV) for0(apy,MAXV)
	for0(any,MAXV) for0(opx,2) for0(opy,2) for0(S,1<>i&1, cy = bpy&1;
		modAddUp(dp[i+1][bpx>>1][bnx>>1][bpy>>1][bny>>1]
			[(cx^mi) ? cx : opx][(cy^mi) ? cy : opy],
				dp[i][apx][anx][apy][any][opx][opy]);
	}
	printf("%dn",((******dp[LOGM])+MOD-1)%MOD);
	return 0;
}