当前位置：网站首页>【luogu P8354】多边形（容斥）（NTT优化DP）

【luogu P8354】多边形（容斥）（NTT优化DP）

2022-07-29 21:48:00 【SSL_TJH】

多边形

题目链接：luogu P8354

题目大意

给你一个正 n 边形，每条边上各自有一些点（数量给出）。
然后你要在点之间连一些边，使得形成一个三角剖分，就是边不相交，而且划分出的每个图形都是三角形。
然后同一条边上的点不能连边，也就是边不能和 n 边形的边重合。
问你合法方案数。

思路

首先如果是正常的三角剖分答案就是卡特兰数。

所以考虑容斥，看一条边会被划分成多少段（就是这一段之间是没有边的），然后再看容斥的。
然后我们发现边与边之间其实没有关系，所以我们可以把每一条边的容斥系数求出来，然后启发式合并（合并过程卷积优化）一下，就可以 O ( m log ⁡ 2 m ) , m = ∑ ( a i + 1 ) O(m\log^2m),m=\sum\limits (a_i+1) O(mlog2m),m=∑(ai​+1) 得到整个多边形的容斥系数。
然后就可以算答案。

接下来考虑如何算一条边的容斥系数：
考虑对于一条边（因为只有一条边所以都是不合法的），我们考虑它的容斥系数：
然后我们会神奇的构造出一个方法：如果跨过一条线的，系数是 1 1 1，跨过两条线的，系数是 − 1 -1 −1，跨过三条以及更多的，系数是 0 0 0。
这个 1 , − 1 1,-1 1,−1 很容易想象出，但是 0 0 0 是为什么呢？

因为这种边里面的点一定会有至少一条跨过两个线的边（因为这样是不会相交的），那你考虑有多少条。
考虑有 k k k 条，考虑钦定多少条，那钦定的就是 − 1 -1 −1，那肯定一半是 1 1 1 一半是 − 1 -1 −1，所以就是 0 0 0 了。
（或者你画个图列举里面的每个连边情况也可以发现所有情况总和是 0 0 0）

那我们就有一个方法：
f i , j f_{i,j} fi,j​ 表示分成 i i i 个段，有 j j j 个线，的容斥系数。
然后你就枚举钦定成了多少个，分成了多少个段，然后转移。
这样是 m 2 m^2 m2 的，考虑优化。

那这个看着就可以换个含义，看看能不能每次加一个位置。
发现可以，可以理解为每个点有三种可能：
第一个是普通的，就左右两边都是同一段。
第二个是不是同一段，但是但是没有被非法段跨过。
第三个就是不是同一段，而且被非法段跨过。

然后你还是这样转移，然后出现第三个就要乘 − 1 -1 −1。
然后你会发现还是 m 2 m^2 m2。

然后再观察一下，发现其实每个点含义相同，那就是可以类似矩阵乘法那样转移！
然后仔细想想，发现可以快速幂的感觉，然后每次可以 O ( n ) O(n) O(n) 来 + 1 +1 +1，那 ∗ 2 *2 ∗2 呢？
发现两个组合起来得到的段数是两半的相加再加上可能中间有的或者减去合并的，那不就是卷积来优化吗！
然后搞就完了，至于 ∗ 2 *2 ∗2 的细节就看代码把。

代码

#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#define mo 998244353
#define cpy(f, g, x) memcpy(f, g, sizeof(int) * (x))
#define clr(f, x) memset(f, 0, sizeof(int) * (x))

using namespace std;

const int N = 1e6 + 100;
const int pN = N * 8;
int jc[N], inv[N], invs[N];
int n, m, f[N], g[N];

int add(int x, int y) {
    return x + y >= mo ? x + y - mo : x + y;}
int dec(int x, int y) {
    return x < y ? x - y + mo : x - y;}
int mul(int x, int y) {
    return 1ll * x * y % mo;}
int ksm(int x, int y) {
    int re = 1; while (y) {
    if (y & 1) re = mul(re, x); x = mul(x, x); y >>= 1;} return re;}
int C(int n, int m) {
    if (m < 0 || m > n) return 0; return mul(jc[n], mul(invs[m], invs[n - m]));}
int Catalan(int x) {
    
	if (x < 0) return 0;
	return mul(C(2 * x, x), inv[x + 1]);
}

struct Poly {
    
	int an[pN], G = 3, Gv;
	vector <int> D[31], Dv[31];
	
	void Init() {
    
		for (int i = 1, d = 0; i < pN; i <<= 1, d++) {
    
			int Gs = ksm(G, (mo - 1) / (i << 1)), Gvs = ksm(Gv, (mo - 1) / (i << 1));
			for (int j = 0, w = 1, wv = 1; j < i; j++, w = mul(w, Gs), wv = mul(wv, Gvs))
				D[d].push_back(w), Dv[d].push_back(wv);
		}
	}
	
	void get_an(int limit, int l_size) {
    
		for (int i = 0; i < limit; i++)
			an[i] = (an[i >> 1] >> 1) | ((i & 1) << (l_size - 1));
	}
	
	void NTT(int *f, int op, int limit) {
    
		for (int i = 0; i < limit; i++) if (an[i] < i) swap(f[i], f[an[i]]);
		for (int mid = 1, d = 0; mid < limit; mid <<= 1, d++) {
    
// int Wn = ksm((op == 1) ? G : Gv, (mo - 1) / (mid << 1));
// int Wn = (op == 1) ? Gs[mid] : Gvs[mid];
			for (int j = 0, R = mid << 1; j < limit; j += R)
// for (int k = 0, w = 1; k < mid; k++, w = mul(w, Wn)) {
    
// int x = f[j | k], y = mul(w, f[j | mid | k]);
				for (int k = 0; k < mid; k++) {
    
// int x = f[j | k], y = mul(tmp[k], f[j | mid | k]);
					int x = f[j | k], y = mul((op == 1) ? D[d][k] : Dv[d][k], f[j | mid | k]);
					f[j | k] = add(x, y); f[j | mid | k] = dec(x, y);
				}
		}
		if (op == -1) {
    
			int limv = ksm(limit, mo - 2);
			for (int i = 0; i < limit; i++) f[i] = mul(f[i], limv); 
		}
	}
	
	void px(int *f, int *g, int limit) {
    
		for (int i = 0; i < limit; i++) f[i] = mul(f[i], g[i]);
	}
	
	void times(int *f, int *g, int n, int m, int T) {
    
		int limit = 1, l_size = 0;
		while (limit < n + m) limit <<= 1, l_size++;
		get_an(limit, l_size);
		clr(f + n, limit - n); clr(g + m, limit - m);
		static int tmp[N]; cpy(tmp, g, m); clr(tmp + m, limit - m);
		NTT(f, 1, limit); NTT(tmp, 1, limit);
		px(f, tmp, limit); NTT(f, -1, limit);
		clr(f + T, limit - T); clr(tmp, limit);
	}
}P;

vector <int> Mul(vector <int> X, vector <int> Y) {
    
	for (int i = 0; i < X.size(); i++) f[i] = X[i];
	for (int i = 0; i < Y.size(); i++) g[i] = Y[i];
	P.times(f, g, X.size(), Y.size(), X.size() + Y.size() - 1);
	vector <int> Z; Z.resize(X.size() + Y.size());
	for (int i = 0; i < Z.size(); i++) Z[i] = f[i];
	while (Z.size() && Z.back() == 0) Z.pop_back();
	return Z;
}

struct Vec {
    
	vector <int> a[2][2];
	
	vector <int>* operator [](int x) {
    return a[x];}
}rem[N];
bool remb[N];

vector <int> operator +(vector <int> x, vector <int> y) {
    
	if (x.size() < y.size()) swap(x, y);
	for (int i = 0; i < y.size(); i++) x[i] = add(x[i], y[i]);
	return x;
}
vector <int> operator -(vector <int> x) {
    
	for (int i = 0; i < x.size(); i++) x[i] = mo - x[i];
	return x;
}

void Init() {
    
	P.Gv = ksm(P.G, mo - 2);
	jc[0] = 1; for (int i = 1; i < N; i++) jc[i] = mul(jc[i - 1], i);
	inv[0] = inv[1] = 1; for (int i = 2; i < N; i++) inv[i] = mul(inv[mo % i], mo - mo / i);
	invs[0] = 1; for (int i = 1; i < N; i++) invs[i] = mul(invs[i - 1], inv[i]);
	P.Init();
	remb[1] = 1;
}

vector <int> Youyi(vector <int> x) {
    
	x.insert(x.begin(), 0); return x; 
}
vector <int> Zuoyi(vector <int> x) {
    
	if (!x.empty()) x.erase(x.begin()); return x;
}

Vec ksmF(int n) {
    
	if (remb[n]) return rem[n]; remb[n] = 1;
	
	if (n & 1) {
    //+1
		Vec X = ksmF(n - 1);
		for (int i = 0; i <= 1; i++) {
    
			rem[n][i][0] = rem[n][i][0] + X[i][0] + Youyi(X[i][0]) + Youyi(X[i][1]); 
			rem[n][i][1] = rem[n][i][1] + X[i][1] + (-X[i][0]); 
		}
	}
	else {
    //*2
		Vec X = ksmF(n / 2);
		for (int i = 0; i <= 1; i++)
			for (int j = i; j <= 1; j++) {
    
				vector <int> A = Mul(X[i][0] + X[i][1], X[0][j] + X[1][j]);
				vector <int> B = Mul(X[i][0], X[1][j]), C = Mul(X[i][1], X[0][j]);//合并段
				rem[n][i][j] = rem[n][i][j] + A + Zuoyi(B) + Zuoyi(C);
			}
		rem[n][1][0] = rem[n][0][1];
		for (int i = 0; i <= 1; i++) {
    
			rem[n][i][0] = rem[n][i][0] + X[i][0] + Youyi(X[i][0]) + Youyi(X[i][1]); 
			rem[n][i][1] = rem[n][i][1] + X[i][1] + (-X[i][0]); 
			rem[n][0][i] = rem[n][0][i] + X[0][i] + Youyi(X[0][i]) + Youyi(X[1][i]); 
			rem[n][1][i] = rem[n][1][i] + X[1][i] + (-X[0][i]); 
		}
	}
	
	rem[n][0][0] = rem[n][0][0] + (vector <int>){
    0, 0, 1};
	rem[n][1][1] = rem[n][1][1] + (vector <int>){
    0, mo - 1};
	return rem[n];
}

vector <int> getF(int n) {
    
	Vec f = ksmF(n);
	vector <int> re; re.resize(n + 1);
	re[1] = 1;//全部是连接点
	for (int i = 0; i <= 1; i++)
		for (int j = 0; j <= 1; j++)
			for (int x = 0; x < f[i][j].size(); x++)
				re[x] = add(re[x], f[i][j][x]);
// for (int i = 0; i < re.size(); i++) printf("%d ", re[i]); printf("\n");
	return re;
}

struct cmp {
    
	bool operator ()(vector <int> x, vector <int> y) {
    
		return x.size() > y.size();
	}
};
priority_queue <vector <int>, vector <vector <int> >, cmp> q;

vector <int> clacF() {
    
	while (q.size() > 1) {
    
		vector <int> X = q.top(); q.pop();
		vector <int> Y = q.top(); q.pop();
// for (int i = 0; i < X.size(); i++) printf("%d ", X[i]); printf("\n");
// for (int i = 0; i < Y.size(); i++) printf("%d ", Y[i]); printf("\n");
		q.push(Mul(X, Y));
	}
	return q.top();
}

int main() {
    
// freopen("polygon.in", "r", stdin);
// freopen("polygon.out", "w", stdout);
	
	Init();
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
    
		int x; scanf("%d", &x); m += x;
		q.push(getF(x));
	}
	
	vector <int> F = clacF();
	int ans = 0;
	for (int i = 0; i < F.size(); i++)
		ans = add(ans, mul(F[i], Catalan(i - 2)));
	printf("%d", ans);
	
	return 0;
}
原网站

版权声明
本文为[SSL_TJH]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_43346722/article/details/126063887

边栏推荐

猜你喜欢

随机推荐