CS Academy Gcd on a Circle（dp + 线段树）

时间：2024-09-19 00:04:02

题意

给你一个长为 \(n\) 的环，你可以把它断成任意 \(k\) 段 \((1 < k \le n)\) ，使得每一段的 \(\gcd\) 都 \(>1\) 。

问总共有多少种方案，对于 \(10^9 + 7\) 取模。

\(n \le 10^5, 2 \le a_i \le 10^9\) 。

题解

首先我们考虑序列上怎么做。

我们令 \(dp_i\) 为到 \(i\) 这个点的方案数， \(pre_i\) 为 \(i\) 向前延伸最长的那个点满足 \((\displaystyle \gcd_{j = pre_i}^{i} a[j]) > 1\) 。

那么

\[\displaystyle dp_i = \sum_{j=pre_i-1}^{i-1} dp_j + [pre_i = 1]
\]

显然这个 \(dp\) 可以用前缀和来进行优化成 \(O(n)\) 的。

至于 \(pre_i\) 的处理可以用线段树求区间 \(\gcd\) ，然后用 two-pointers 来扫端点就行了，是 \(O(n( \log n + \log V))\) 的（ \(\displaystyle V = \max_{i=1}^{n} a_i\) ）。

好像利用 \(\gcd\) 的一些奇怪势能分析可以证明。

然后如果成环的话，我们只需要多考虑一种情况也就是 \(1,n\) 相连。

对于这种情况，可以考虑枚举最后面有 \(k\) 个数和 \(n\) 相连就行了。

然后每次计算的时候，可以类似于前面 \(dp\) 的计算就行了，但是要注意一下，那个 \([pre_i = 1]\) 要转化成后面 \(k\) 个数与前缀的 \(\gcd\) 是否 \(>1\) 。（也就是我们强行把后 \(k\) 个数当做一个整体提到前面就行了）

然后这样直接做是 \((n^2 \log V)\) 的，不够优秀。

但是我们发现很多数其实没有什么本质区别的，也就是后缀 \(\gcd\) 相同的一部分点可以一起计算。

这样的话，我们可以只在 \(\gcd\) 转折处，以及 \(0\) 号点计算就行了（因为要考虑上 \(1\) 向后那一片 \(\gcd\) 相同的数）。然后复杂度就是 \(O(n \log^2 V)\) 的了。

因为一个点向一端不断延伸，它的 \(\gcd\) 变换次数是 \(O(\log V)\) 的，因为每次变化至少会对于其中一个指数 \(-1\) 。

还有个特殊情况，也就是全部 \(\gcd > 1\) 的情况，需要将方案数 \(- (n - 1)\) 。（因为至少要分成 \(1\) 段）

最后就是 \(O(n (\log n + \log V) \log V)\) 的。

总结

对于一类划分环计数的题目，可以考虑枚举最后面那一段和前面相连的长度，然后直接一遍 \(O(n)\) 计数。

对于有些关于 \(\gcd\) 的题可以利用 \(\gcd\) 变换次数不超过 \(O(\log V)\) 来做。

代码

代码还是很好写的，可以参考一下。（其实博主参考了一下 ysgs 大佬的代码　）

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

#define Cpy(a, b) memcpy(a, b, sizeof(a))

#define debug(x) cout << #x << ": " << x << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

inline bool chkmin(int &a, int b) {return b < a ? a = b, 1 : 0;}

inline bool chkmax(int &a, int b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x = 0, fh = 1; char ch = getchar();

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') fh = -1;

    for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);

    return x * fh;

}

void File() {

#ifdef zjp_shadow

	freopen ("gcd-on-a-circle.in", "r", stdin);

	freopen ("gcd-on-a-circle.out", "w", stdout);

#endif

}

#define lson o << 1, l, mid

#define rson o << 1 | 1, mid + 1, r

const int N = 1e5 + 1e3, Mod = 1e9 + 7;

int a[N];

struct Segment_Tree {

	int Gcd[N << 2];

	void Build(int o, int l, int r) {

		if (l == r) { Gcd[o] = a[l]; return ; }

		int mid = (l + r) >> 1;

		Build(lson); Build(rson); Gcd[o] = __gcd(Gcd[o << 1], Gcd[o << 1 | 1]);

	}

	int Query(int o, int l, int r, int ql, int qr) {

		if (ql <= l && r <= qr) return Gcd[o];

		int mid = (l + r) >> 1;

		if (qr <= mid) return Query(lson, ql, qr);

		if (ql > mid) return Query(rson, ql, qr);

		return __gcd(Query(lson, ql, qr), Query(rson, ql, qr));

	}

} T;

inline int Add(int a, int b) { return (a += b) >= Mod ? a - Mod : a; }

int n, sum[N], dp[N], pre[N];

void Calc(int cur) {

	sum[0] = 1;

	For (i, 1, n) {

		cur = __gcd(cur, a[i]);

		if (cur > 1) dp[i] = sum[i - 1];

		else dp[i] = Add(sum[i - 1], Mod - sum[max(0, pre[i] - 2)]);

		sum[i] = Add(sum[i - 1], dp[i]);

	}

}

int main () {

	File();

	n = read();

	For (i, 1, n) a[i] = read(); T.Build(1, 1, n);

	pre[1] = 1;

	For (i, 2, n)

		for (pre[i] = pre[i - 1]; pre[i] < i; ++ pre[i])

			if (T.Query(1, 1, n, pre[i], i) > 1) break;

	int Last = n, suf = 0, cur, ans = 0;

	Fordown (i, n, 1) {

		cur = __gcd(a[i], suf);

		if (cur != suf || i == 1) {

			Calc(suf); ans = Add(ans, Add(sum[Last], Mod - sum[i - 1]));

			Last = i - 1; suf = cur;

		}

	}

	printf ("%d\n", Add(ans, (Mod - (T.Gcd[1] > 1 ? (n - 1) : 0))));

    return 0;

}

相关文章