题解 P7800 [COCI2015-2016#6] PAROVI

​​题目传送门​​

算法分析：线性 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,m}\)，\(cnt\) 为互质对的总数。于是有：

\[\begin{cases}dp_{i,j}=dp_{i,j}+dp_{i-1,j}\\dp_{i,R_{i}}=dp_{i,R_{i}}+dp_{i,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:

#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 记录​​

不过还有一种比较朴素的搜索算法（模拟赛时想出来的乱搞算法）。为了避免重复，我们限定使用的的线段数量，类似于 ​

​ID​

​，记忆化搜索，记 \(dp_{fro,r,res}\) 表示上一条线段是 \(fro\)，当前已经覆盖 \(1\to r\)，还要选 \(res\) 条线段的情况数。这里也给出代码。

code2:

#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​​

跑得慢死了。

欢迎交流套路，请点个赞哦~

作者：枫のDark​，转载请注明原文链接​