P1148 环上GCD
题意简述
\(n\) 个数 \(a_1,a_2,\cdots,a_n\)，排成一个环，求出分割后每段的 \(\gcd\) 均大于1的方案数。
\(n\le 10^5\)
解题思路
看到这题，首先想到dp，但是发现如果断环成链会出现方案数被多次计算。
我们知道一定有段数包含 \(a_1\)，我们暴力枚举从 \(a_n\rightarrow a_2\) 的前缀，若前缀为 \(a_x\rightarrow a_n\)，那么从 \(a_1\) 开始暴力dp到 \(a_{x-1}\) 就行了。
但是这么做的时间复杂度仍然是 \(O(n^3)\), 我们发现从 \(a_n\) 到 \(a_2\) 枚举前缀时 \(gcd(\{a_x,\cdots, a_n\})\) 单调不升，并且每次下降后的 \(gcd'\le \frac{gcd}{2}\)，所以可以在 gcd 没变时使用上一次的dp值，变的时候再重新暴力dp，当 \(gcd=1\) 时退出，时间复杂度降为 \(O(n^2\log n)\)。
我们发现，dp的转移式是 \(f_i = \sum\limits_{j < i}f_j[\gcd(a_{j+1},\cdots,a_i)>1]\)，又有从 \(i\) 到 \(j\), \(\gcd\) 单调不升，所以我们可以使用双指针，但是发现 \(\gcd\) 没有逆运算，所以只能暴力 \(st\) 表，因为每次dp时 \(j\) 指针只会移动最多 \(n\) 次，所以复杂度来到 \(O(n\log^2 n)\)，可以通过。
细节
- 取模，负数 \(\rightarrow\) 正数
- dp时发现状态定义是在 \(a_i,a_{i+1}\) 间切断，所以要注意 \(f_0=f_1=1\)。
- 注意每次dp时 \(a_1\) 相当于 \(\gcd(\{a_1,a_x,a_{x+1},\cdots,a_n\})\)，所以st表求 \(\gcd\) 时要特判一下。
P1147 Assembly
这场比赛里最难的题。
题意简述
给你一个 \(R\times C\) 的网格，\(n\) 个点，坐标 \(R_i,C_i\)，两个点 \(x,y\) 之间能直接通行当且仅当 \((R_x>R_y\land C_x>C_y)\lor(R_x<R_y\land C_x<C_y)\)。
求出对于每个点，其他点到这个点经过的边数之和。
\(R,C\le 2.5\times 10^3,n\le 2.5\times 10^5\)
解题思路
对于上图，绿色区域代表可以和 \((4,5)\) 直接连接，那么如何处理红色区域中的点呢？
我们不妨找一下需要两步的点都在哪：
我们发现，要走两步的点就是绿色区域内的点可以直接到达的点，如果绿色区域内的还到达不了，就需要走三步，即黄色区域。
我们发现，黄色区域一定包含在红色区域中，所以我们想到dp。
令 \(f1_{i,j}\) 表示左下角区域为 \(i\le x\le R,1\le y\le j\)，\(f2_{i,j}\) 表示右上角区域为 \(1\le x\le i,j\le y\le C\)。
那么我们就有了状态，怎么设计转移方程呢？
我们发现，若有多个点均在 \(x\) 步能走到的范围（如上图），那么对于左下角的区域来说，一定是最左侧和最下面的点（橙色点）最优，因为选这两的点会尽可能的缩小 \(x+1\) 步能走到的范围，答案显然较非最左/下侧的蓝色点更优（棕、黄色区域分别表示选择蓝、橙色点的 \(x+1\) 步区域，黄色区域显然小于棕色区域，所以黄色区域更优）。
所以我们令 \(up,down,left,right\) 分别表示 \(x\) 步区域中最 上/下/左/右 侧的点，有 \(f1_{x,y}=f1_{down,left}+cnt_{down,left}^{\dagger}+sz_{x,y}^{\ddagger}-cnt_{x,y}\)。
加减 \(cnt\) 是什么意思呢？因为 \(f1_{x,y}\) 表示 \((x,y)\) 对每个点要比1多走几步才能到达的和，需要减去 \((x,y)\) 的 \(cnt\)，所以从子状态转移时也要加上子状态的 \(cnt\)。
同理，\(f2_{x,y}=f2_{up,right}+cnt_{up,right}+sz_{x,y}-cnt_{x,y}\)
\(\dagger\) : \(cnt_{x,y}\) 表示 \((x,y)\) 是否有点存在。
\(\ddagger\) : \(sz_{x,y}\) 表示 \((x,y)\) 左下/右上的点的总个数（定义视计算的是左下角还是右上角的区域而定）
细节
- 注意刚才着重讲的 \(cnt\) 加减
- 在处理 \(up,down,left,right\) 时如果有赋极大值，那么要记得和当前状态取 \(\min/\max\)，否则不满足子状态比当前状态范围小的要求。
代码
P1148 环上GCD
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e5 + 5, K = 20, p = 1e9 + 7;
int a[N], f[N], n, ans;
int st[N][K], hbit[N], ok = 0;
int getgcd(int l, int r, int g1)
{
int len = hbit[r - max(l, 2ll) + 1];
int g = __gcd(st[max(l, 2ll)][len], st[r - (1 << len) + 1][len]);
if(l == 1) return __gcd(g, g1);
else return g;
}
void calc(int x, int g)
{
memset(f, 0, sizeof f);
int w = 1;
f[0] = f[1] = 1;
for(int i = 1, j = 1; i < x; i ++)
{
while(j + 1 < x && getgcd(i, j + 1, g) > 1)
{
j ++;
f[j] = (w + f[i - 1]) % p;
w = (w + f[j]) % p;
}
w = (w - f[i]) % p;
}
ans = (ans + f[x - 1] - ok) % p;
}
void init()
{
int lim = 1, p = -1;
for(int i = 1; i <= n; i ++)
{
if(i == lim) lim <<= 1, p ++;
hbit[i] = p;
}
for(int i = 1; i <= n; i ++)
st[i][0] = a[i];
for(int j = 1; j < K ; j ++)
for(int i = 1; i <= n; i ++)
st[i][j] = __gcd(st[i][j - 1], st[min(n, i + (1 << j - 1))][j - 1]);
}
signed main()
{
#define fio(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout)
fio(gcd);
ios::sync_with_stdio(0);cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
init();
ok = st[1][K - 1] > 1;
int g = a[1], lstg = g;
calc(n + 1, g);
for(int i = n; i > 1; i --)
{
g = __gcd(g, a[i]);
if(g == 1) break;
if(g != lstg) calc(i, g);
else ans = (ans + f[i - 1] - ok) % p;
lstg = g;
}
cout << ((ans + ok) % p + p) % p;
return 0;
}
P1147 Assembly
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2505, M = 250005;
int f1[N][N], f2[N][N], n, x[M], y[M];
int cnt[N][N], s[N][N];
int u[N][N], d[N][N], l[N][N], r[N][N];
//fastio here
signed main()
{
#define fio(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout)
fio(assembly);
ios::sync_with_stdio(0);cin.tie(0);
int V = 0;
read(n);
for(int i = 1; i <= n; i ++)
read(x[i], y[i]), cnt[x[i]][y[i]] ++, V = max(V, max(x[i], y[i]));
for(int i = 0; i <= V + 1; i ++)
for(int j = 0; j <= V + 1; j ++)
{
if(cnt[i][j]) u[i][j] = i, l[i][j] = j;
else u[i][j] = V + 1, l[i][j] = V + 1;
if(i) u[i][j] = min(u[i][j], u[i - 1][j]), l[i][j] = min(l[i][j], l[i - 1][j]);
if(j) l[i][j] = min(l[i][j], l[i][j - 1]), u[i][j] = min(u[i][j], u[i][j - 1]);
}
for(int i = V + 1; i >= 0; i --)
for(int j = V + 1; j >= 0; j --)
{
if(cnt[i][j]) d[i][j] = i, r[i][j] = j;
else d[i][j] = 0, r[i][j] = 0;
if(i <= V) d[i][j] = max(d[i][j], d[i + 1][j]), r[i][j] = max(r[i][j], r[i + 1][j]);
if(j <= V) r[i][j] = max(r[i][j], r[i][j + 1]), d[i][j] = max(d[i][j], d[i][j + 1]);
}
for(int i = 1; i <= V; i ++)
for(int j = V; j >= 1; j --)
{
s[i][j] = s[i - 1][j] + s[i][j + 1] - s[i - 1][j + 1] + cnt[i][j];
int i0 = min(i, u[i - 1][j - 1]), j0 = max(j, r[i + 1][j + 1]);
f1[i][j] = s[i][j] - cnt[i][j] + f1[i0][j0] + cnt[i0][j0];
}
memset(s, 0, sizeof s);
for(int i = V; i >= 1; i --)
for(int j = 1; j <= V; j ++)
{
s[i][j] = s[i + 1][j] + s[i][j - 1] - s[i + 1][j - 1] + cnt[i][j];
int i0 = max(i, d[i + 1][j + 1]), j0 = min(j, l[i - 1][j - 1]);
f2[i][j] = s[i][j] - cnt[i][j] + f2[i0][j0] + cnt[i0][j0];
}
for(int i = 1; i <= n; i ++)
cout << n - 1 + f1[x[i]][y[i]] + f2[x[i]][y[i]] << "\n";
return 0;
}