D&D 题解

· · 题解

隐藏的视频

标题 \text{D\&D} 的含义是 \text{Darling Dance}。

简单喵喵题

本题是一道结论题，本题只介绍 100\% 的做法，这里先放上结论

划分完以后每一个集合的装饰子集与原数列的装饰子集相同。

一个直观的证明方法就是把每个数化为二进制。下面讲一讲严谨的证明。

我们设原数组的装饰子集为 F。

结论 1：假设 x\in F 则 x 在划分后的装饰子集中出现。

这个结论是显然的，反证法即可。

结论 2：假设 x\not \in F 则 x 不在划分后的装饰子集当中出现。

反之，必然有一个 y\in F,x|y=y。由结论 1，必然有 y 在每一个装饰子集当中出现，这与 x 存在于装饰子集当中矛盾。

结论 3：对于原数组的子集 B，只要 F\subseteq B 那么 B 的可爱子集是 F。

这个结论也是显然的。

有了结论，我们现在进一步解决该问题。

  1. 快速求出原数组的装饰子集

考虑把 a 从大到小排，丢进去 dfs 里面处理，具体流程如下：

void dfs(int x){
    if(flag[x]) return;
    flag[x]=true;
    for(int i=0;i<=20;i++)
        if(x&(1<<i))
            dfs(x-(1<<i));
    return;
}

对于 x，若丢进去之前其 \text{flag} 为假，那么它就是装饰子集当中的元素。

  1. 快速求出划分方案

这里发现只要 [l,i] 能划分为合法的装饰子集，那么 [l-1,i] 也可以划分为合法的装饰子集。那么定义 L_i 为最大的 x 使得 a[x,l] 是合法的装饰子集。那么得到转移公式：

f_i=\sum_{j=0}^{L_i-1} f_j

用前缀和优化即可。

参考代码

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1e6+5;
const int MOD=1e9+7;
int n;int a[MAXN],b[MAXN];
bool flag[MAXN];int col[MAXN];
int f[MAXN];int s[MAXN];int cnt=0,tmp=0;
int res[MAXN];
int L[MAXN];//L[i]表示最大的x使得[x,i]构成一个装饰子集. 
void dfs(int x){
    if(flag[x]) return;
    flag[x]=true;
    for(int i=0;i<=20;i++)
        if(x&(1<<i))
            dfs(x-(1<<i));
    return;
}
void cute_sub(){
    sort(b+1,b+n+1);
    for(int i=n;i>=1;i--)
        if(!flag[b[i]]){
            col[b[i]]=++cnt;
            dfs(b[i]);
        }
    for(int i=1;i<=n;i++)
        a[i]=col[a[i]];
    return;
}
void find_left(){
    int l=0;
    for(int i=1;i<=n;i++){
        if(a[i]!=0&&res[a[i]]++==0) tmp++;
        if(l==0&&tmp<cnt) L[i]=n+2;
        while(tmp==cnt){
            l++;
            if(a[l]!=0&&--res[a[l]]==0) tmp--;
        }
        if(!L[i]) L[i]=l;
    }
    return;

}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],b[i]=a[i];
    cute_sub();
    find_left();
    s[0]=1;
    for(int i=1;i<=n;i++)
        s[i]=(s[i-1]+s[L[i]-1])%MOD;
    cout<<(s[n]-s[n-1]+MOD)%MOD;
    return 0;
}