P5 [COCI2015-2016#6] PAROVI

· · 题解

题目描述

然后轮到 $Slavko$。他需要找到一个 $x∈[2,n] $ 使得对于每组 $(a,b)$ 都满足以下两个条件之一： - $a,b<x

如果 Slavko 找不到满足条件的 x 值，则表示 Mirko 获得胜利。现在请你求出 Mirko 获胜的不同情况的总数，在对 10^9 取模后告诉他。

对于 100% 的数据，1≤N≤20。

调了大半天...

Step 1：

发现 n 最大只有 20 ，再跑一下可以发现最多只有 127 种互素数对，所以可以先双循环枚举出所有 n 以内互素对。

Step 2:

现在可以转化一下问题。实际上他要求的是给定一个定长区间段，现在你有很多个小区间，让你选择任意个(不能不选)区间，使他们能覆盖所有地方。求能实现的选择方案数。

这里要注意他覆盖的左端点是开区间，所以要加一。

if(gcd(i,j)==1) d[++cnt].x=i+1,d[cnt].y=j;

我第一反应是递推，不过是从后往前推的。当时考虑的是 f[i] 统计方案数，然后对于所有从 i 开始的区间，都去做一个累加 f[l]+=f[r], 但是后来发现这样子是会出大问题的，因为你统计次序无法保证，也就是说，你可能在选完某些区间已经满足要求后，还可以继续选，但是你递推时候你可能无法保证能继承得到。

然后我就卡了半天，想起来之前好像做过几道题，思维是反着来的，于是就有了下面这种做法。

Step 3:

到这一步实际上就有很多做法了，题解里面基本都是一些神奇的 dp (所以我嫖不了只能自己干了）。

不难发现总方案数：假设现在有 k 段小区间，如果选一段，那就是 C_k^1 , 如果选两段，就是 (n-1)+(n-2)+...+1 也就是 C_k^2 , 发现实际上总方案数是 \sum C_k^i (i∈[1,k]), 二项式好像有个模型是 2^k 等于这玩意再加个 C_k^0 也就是 1，不过手推也行。总之，总方案数 ans=2^k-1。

所以现在就只用算违法的方案数了。

Step 4:

然后我就想到了记忆化搜索。(因为注意到了Step 2中求小区间时左端点自动升序)

不过我第一次写的时候一直少考虑了一维，所以寄得很惨。

1.第一维，思考一下可以发现，这题很像 NOIP2016愤怒的小鸟，对于一段区间，如果现在不选，那么以后如果反过来选就是多余的操作，所以不妨第一维定成当前搜到了哪个编号的区间。--pos

2.第二维，如果到了某个点，肯定是需要去考虑当前搜出来的组合出来的区间最后端在哪。比如到了某个点 o , 可能此时的区间最右端在 14 , 也可能在 19 , 如果忽略了这一维度，就会出错。--r

3.第三维，不难发现，既然左端点是递增的，那么如果出现了第二维维护的 当前选择的连续区间的最右端点 和新选择的小区间之间出现了空隙，那么以后的所有小区间都不可能再弥补这个空隙了。也就是说，第三维是个 bool 类型，维护的是搜到当前是否满足题意要求。那如果满足，就看下一次是否满足，不满足就随便选了，后面再怎么选都是不合法的。--yon

所以就欧了 , 时间好像也不是很慢。

我一开始还有个错点，就是把 Mod 定义成了 1e9+9 , 焯 。

还有一点细节，就是取模可能取成 0 , 所以要用什么做个标记 vis , 以及在更新右端点时要取 max。

#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N=25;
const int maxn=130;
const int Mod=1000000000;

int n,cnt;
struct D{int x,y;}d[maxn];

inline int gcd(int a,int b){return b?gcd(b,a%b):a;}
inline int Max(int A,int B){return A>B?A:B;}

bool vis[maxn][N][2];
ll f[maxn][N][2];//到某个点状态为0/1的不合法方案数 
inline ll dfs(int pos,int r,bool yon){
    if(r==n&&!yon) return 0;//cut
    if(vis[pos][r][yon]) return f[pos][r][yon];
    if(pos>cnt) return yon;
    for(int i=pos;i<=cnt;++i){
        if(!yon&&d[i].x<=r+1)
            f[pos][r][yon]=(f[pos][r][yon]+dfs(i+1,Max(d[i].y,r),false))%Mod;
        else
            f[pos][r][yon]=(f[pos][r][yon]+dfs(i+1,0,true))%Mod;
    }
    f[pos][r][yon]+=(r==n&&!yon)?0:1;
    vis[pos][r][yon]=true;
    return f[pos][r][yon]%=Mod;
}

int main(){
//  freopen("parovi.in","r",stdin);
//  freopen("parovi.out","w",stdout);
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
            if(gcd(i,j)==1) d[++cnt].x=i+1,d[cnt].y=j;

    ll ans=1;
    for(int i=1;i<=cnt;++i) ans=(ans<<1)%Mod;

    ans=ans-dfs(1,1,false);
    cout<<(ans+Mod)%Mod<<'\n';
    return 0;
}

· EOF