[CF1290F]Making Shapes

[CF1290F]Making Shapes,第1张

[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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5702882.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存