題解 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​，轉載請注明原文連結​