[COCI 2015/2016 #6] PAROVI
[COCI 2015/2016 #6] PAROVI
Problem
这是一道加强版 时空与数据
【时空限制】1.00s 64.00MB
【题目描述】
\(\text{Mirko}\) 和 \(\text{Slavko}\) 在玩一个游戏，先由 \(\text{Mirko}\) 在 \(1\dots N\) 中选出几组互质的数（不能不选，且每组中的数不得相同）。例如当 \(N=5\) 时，\(\text{Mirko}\) 可以选择 \(\big\{\{1,2\},\{3,4\},\{2,5\},\{3,5\},\cdots\big\}\) 中的几组。
然后轮到 \(\text{Slavko}\)。他需要找到一个 \(x\in \big[2,N\big]\) 使得对于每组 \(\{a,b\}\) 都满足以下两个条件之一：
-
\(a\)，\(b<x\)
-
\(a\)，\(b\ge x\)
例如，如果 \(\text{Mirko}\) 选了 \(\big\{\{1,2\},\{3,4\}\big\}\)，那么 \(x\) 可以等于 \(3\)。
如果 \(\text{Slavko}\) 找不到满足条件的 \(x\) 值，则表示 \(\text{Mirko}\) 获得胜利。现在请你求出 \(\text{Mirko}\) 获胜的不同情况的总数，在对 \(M=10^9\) 取模后告诉他。
【输入格式】
第一行包含一个整数 \(N\)。
【输出格式】
第一行输出一个整数，为 \(\text{Mirko}\) 获胜的不同情况的总数对 \(10^9\) 取模后的值。
【数据范围】
按子任务捆绑：
子任务1: 对于 \(30\) 分，\(1\le N\le 7\)。
子任务2: 对于 \(30\) 分，\(1\le N\le 20\)。
子任务3: 对于 \(40\) 分，\(1\le N\le 10^4\)。
Solution
观察到选择每两个互质的数 \([l,r]\) 等于 \(x\in[l,r]\) 无法选择
考虑转化为区间覆盖问题，要求 \([1,N]\) 被完全覆盖
朴素预处理
直接使用__gcd判断是否互质
显然在本题不可做
考虑使用欧几里得算法求解 gcd，并且使用记忆化对递归进行优化
总的时间复杂度不会超过 \(n^2\)
但是空间会炸 （好的题目）
优化预处理
考虑逆向欧几里得算法的过程
直接将互质二元组存储到队列中
使用 bitset 进行空间压缩，储存一个二维数组表示是否互质
可以利用一个性质：
若 \((a, b)\) 互质，则 \((a, a+b)\) 和 \((b, a+b)\) 也互质。
因此从 \((1, 1)\) 开始，通过 \((a, b) \to (a, a+b)\) 和 (a, b) \to (b, a+b) 可以生成所有互质对
一个经典结论是：n 以内互质对的数量约为 3n² / π² ≈ 0.304 n²，
时间复杂度 \(O(0.304n^2)\)
很遗憾，因为 缓存命中率 太低 以及 STL 太慢 队列太大容易爆空间过不了
正解预处理
使用欧拉筛筛出素数，并且预处理出每个数的最小质因子
对于每一个数，我们可以将它除去它的最小质因子
这样我们就可以在 \(O(nlog(n))\) 的时间求出每个数的质因数
对于每个质因数数开一个bitset，表示它的倍数
对于每一个数，开一个bitset表示与它不互质的数
遍历它的质因数，将它的bitset与质因数的倍数做或运算
总体时间复杂度 \(O(n^2/w)\) 时空上可以接受
考虑朴素DP
直接从 \([l,r]\) 入手定义状态是不好定义的，因为要考虑许多的情况
按照 \(r\) 排序，方便DP
设 \(f_{i,j}\) 表示前 \(i\) 条线段覆盖了 \([1,j]\) 的方案数
这里第一项的意义是不选择这条线段
二三项讨论了选择线段时覆盖的问题
优化DP
以上的DP足够通过原题，但无法通过加强版
时间复杂度最高 \(0.304n^3\) 需要优化
我们观察到转移只依赖于上一行，空间可以用滚动数组优化掉第一维变成 $
但更关键的是，对于每个 l，所有以 l 为左端点的线段 (l, r)，它们的转移可以一起处理。
有了以上的铺垫
将状态重新定义为 \(f_j\) 表示当前覆盖到前缀 \([1, j]\) 的方案数。
这里有一个理论上的范式
对于所有的 \((l,r)\)，都有
new_f[r] += sum(f[l .. r-1])
new_f[j] += f[j] for j ≥ r
并且所有 j > l 的状态在考虑完 (l, r) 后
如果还有后续线段，需要乘以 2（因为可以选择或不选这个线段，且不选时保持原状态）
我们就可以得出如下实现 （逆序循环是因为滚动数组）
Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 10, p = 1e9;
int n, f[N];
int mp[N];
vector<int> pm[N];
bitset<N> hp[N], nc[N];
void pre(int n) {
vector<int> prime;
for (int i = 2; i <= n; i++) {
if (!mp[i]) {mp[i] = i, prime.emplace_back(i);};
for (auto p : prime) {
int v = 1 * p * i;
if (v > n) break;
mp[v] = p;
if (p == mp[i]) break;
}
}
for (int i = 2; i <= n; i++) {
int t = i;
while (t > 1) {
int x = mp[t];
pm[i].push_back(x);
hp[x][i] = 1;
while (t % x == 0) t /= x;
}
}
for (int i = 1; i <= n; i++) {
bitset<N> tmp;
for (int x : pm[i]) tmp |= hp[x];
tmp[i] = 0;
nc[i] = tmp;
}
}
bool cp(int x, int y) {
return !nc[x][y];
}
signed main() {
cin >> n;
if (n == 1) { cout << 0; return 0;}
pre(n);
f[1] = 1;
for (int i = 1; i <= n; i++) {
int s = 0;
for (int j = i; j <= n; j++) s = (s + f[j]) % p;
for (int j = n; j > i; j--) {s -= f[j]; if (cp(i, j)) f[j] = (f[j] * 2 + s) % p;}
for (int j = i + 1, mul = 1; j <= n; j++) {f[j] = (f[j] * mul) % p; if (cp(i, j)) mul = mul * 2 % p;}
}
cout << (f[n] + p) % p;
return 0;
}
浙公网安备 33010602011771号