题解 P7800 [COCI2015-2016#6] PAROVI
☯☯枫☯☯
·
·
题解
题目传送门
更好的阅读体验
upd：
$[\texttt{2021.10.7}]$ 修改了一处下标错误。
## 算法分析：线性 dp
拿到题目首先观察数据范围，发现 $1\le n\le20$，因此我们可以先将所有的满足条件的互质的数预处理出来（以下称这些满足条件的组为“互质对”）。需要注意的一点是，$\{1,1\}$ 这组不满足条件。当 $n=20$ 时，共有 $127$ 组。
接着我们考虑 $\text{Mirko}$ 在什么条件下能获得胜利。
- 如果 $\text{Mirko}$ 没有选包含 $1$ 的互质对，那么，不论他如何选，所有被选的互质对必定满足 $a,b \ge 2$。也就是说，$\text{Slavko}$ 只需令 $x=2$。在这种情况下，$\text{Mirko}$ 无法获胜。
- 如果 $\text{Mirko}$ 没有选包含 $n$ 的互质对，与上一中情况类似，所有被选的互质对必定满足 $a,b<n$。也就是说，$\text{Slavko}$ 只需令 $x=n$。在这种情况下，$\text{Mirko}$ 同样无法获胜。
- 如果 $\text{Mirko}$ 选的互质对中包含以下情况：
> 记他选的某两对互质对 $\{a,b\},\{c,d\}$ 且满足 $a<b<c<d$。
那么 $\text{Slavko}$ 只需令 $x=c$，那么 $\text{Mirko}$ 依然无法获胜。
综合以上三种情况，我们发现，若要使 $\text{Mirko}$ 获胜，不能存在上述三种情况的任意一种。
我们把一组互质对看做一条 $a\to b$ 的线段，那么这个问题就转化为区间覆盖问题。即：
> 在给定线段中选出若干条，求完全覆盖 $1\to n$ 这个区间的方案数。
针对此问题，我们先将所有线段按右端点排序。可设 $dp_{i,j}$ 为选到第 $i$ 条线段，覆盖了 $1\to j$ 这个区间的方案数。初始化 $dp_{0,1}=1$，答案为 $dp_{cnt,n}$，$cnt$ 为互质对的总数。于是有：
$$\begin{cases}dp_{i,j}=dp_{i,j}+dp_{i-1,j}\\dp_{i,R_{i}}=dp_{i,R_{i}}+dp_{i-1,j}&L_{i}<=j\\dp_{i,j}=dp_{i,j}+dp_{i-1,j}&L_{i}>j\end{cases}$$
其中 $L_i$，$R_i$ 分别表示第 $i$ 条线段的左、右端点。
**code:**
```cpp
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define F(i,a,b) for(reg int i=(a);i<=(b);++i)
using namespace std;
bool beginning;
inline int read();
const int N=150,mod=1e9;
int n,cnt;
struct P {
int x,y;
bool operator <(const P& a)const {
return y<a.y;
}
} a[N];
namespace Dp {
ll dp[N][25];
void main() {
dp[0][1]=1;
F(i,1,cnt) {
F(j,1,n) {
dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
if(a[i].x<=j)dp[i][a[i].y]=(dp[i][a[i].y]+dp[i-1][j])%mod;
else dp[i][j]=(dp[i][j]+dp[i-1][j])%mod;
}
}
printf("%lld\n",dp[cnt][n]);
}
}
bool ending;
int main() {
// system("color fc");
// printf("%.2lfMB\n",1.0*(&beginning-&ending)/1024/1024);
n=read();
F(i,1,n) {
F(j,i+1,n) {
int gcd=__gcd(i,j);
if(gcd==1)a[++cnt]= {i,j};
}
}
sort(a+1,a+cnt+1);
Dp::main();
return 0;
}
inline int read() {
reg int x=0;
reg char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
```
[AC 记录](https://www.luogu.com.cn/record/55596920)
不过还有一种比较朴素的搜索算法~~（模拟赛时想出来的乱搞算法）~~。为了避免重复，我们限定使用的的线段数量，类似于 `ID`，记忆化搜索，记 $dp_{fro,r,res}$ 表示上一条线段是 $fro$，当前已经覆盖 $1\to r$，还要选 $res$ 条线段的情况数。这里也给出代码。
**code:**
```cpp
#include<bits/stdc++.h>
#define ll long long
#define reg register
#define F(i,a,b) for(reg int i=(a);i<=(b);++i)
using namespace std;
bool beginning;
inline int read();
const int N=150,mod=1e9;
int n,cnt;
struct P {
int x,y;
} a[N];
ll dp[N][25][N];
ll dfs(int fro,int r,int res) {
if(!res)return r>=n;
if(fro>=cnt)return 0;
if(~dp[fro][r][res])return dp[fro][r][res];
ll ans=0;
F(i,fro+1,cnt) {
if(a[i].x<=r) {
ans+=dfs(i,max(a[i].y,r),res-1);
ans%=mod;
}
}
return dp[fro][r][res]=ans;
}
bool ending;
int main() {
// system("color fc");
// printf("%.2lfMB\n",1.0*(&beginning-&ending)/1024/1024);
n=read();
F(i,1,n) {
F(j,i+1,n) {
int gcd=__gcd(i,j);
if(gcd==1)a[++cnt]= {i,j};
}
}
ll ans=0;
memset(dp,-1,sizeof(dp));
F(i,1,cnt) {
ans+=dfs(0,1,i);
ans%=mod;
}
printf("%lld\n",ans);
return 0;
}
inline int read() {
reg int x=0;
reg char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x;
}
```
[AC](https://www.luogu.com.cn/record/55135118)
~~跑得慢死了。~~
欢迎交流套路，请点个赞哦~