「CTSC 2017」吉夫特

发表于 | | 阅读次数:
字数统计: 595 字

Description

题目链接：Luogu 3773

给定一个长度为 $n$ 的数列 $a_i$，求有多少个长度大于等于 $2$ 的不上升子序列 $a_{b_1},a_{b_2},\cdots,a_{b_k}$ 满足

输出这个个数对 $1000000007$ 取模的结果。

数据范围：$1\le n\le 211985$，$1\le a_i\le 233333$。所有的 $a_i$ 互不相同。

Solution

看到这么大一串累乘式子，肯定要先寻找规律呀！

由于 $\bmod 2$ 的值为 $1$，那么意味着式子的值为奇数。又因为 $2$ 是质数，所以根据 $\text{Lucas}$ 定理，可以得到

我们将 $n$ 和 $m$ 化为二进制。当 $\binom{n}{m}$ 为奇数时，只需要满足没有任何一位上 $n$ 是 $0$ 且 $m$ 为 $1$（如果某一位上 $n$ 是 $0$ 而 $m$ 是 $1$，那么 $\binom{n}{m}$ 根据 $\text{Lucas}$ 定理展开后必有 $\binom{1}{0}$ 这一项，原式为偶数）。

经过上述分析，我们就可以发现：当 $\binom{n}{m}$ 为奇数时，当且仅当 $m\ \text{AND}\ n=m$，也就是说 $m$ 在二进制下是 $n$ 的子集。

于是我们就把这个问题转化成了一个可以 $\text{DP}$ 的问题。接下来定义 $\text{DP}$ 状态：$f[i]$ 表示以 $i$ 这个数结尾有多少个长度至少为 $1$ 的序列（注意：这里使用“至少为 $1$”可以方便转移）。转移时枚举 $a_i$ 的子集 $j$，那么在 $j$ 之前可以接 $f[a_i]+1$ 种序列（$f[a_i]$ 为以 $a_i$ 结尾的序列数量，而 $1$ 则为不选择 $a_i$）。

注意：由于状态为“至少为 $1$”的序列个数，所以最终答案要减去 $n$。

时间复杂度：$O(n\cdot 2^{cnt(a_i)})$（其中 $cnt(x)$ 表示 $x$ 在二进制下 $1$ 的个数）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
#include <cstdio>
const int N=3e5+5;
const int mod=1e9+7;
int n,f[N];
int main() {
    scanf("%d",&n);
    int ans=0;
    for(int x,i=1;i<=n;++i) {
        scanf("%d",&x);
        int sum=f[x]+1;
        for(int j=x;j;j=(j-1)&x) {
            f[j]+=sum;
            if(f[j]>=mod) f[j]-=mod;
        }
        ans+=sum;
        if(ans>=mod) ans-=mod;
    }
    ans-=n;
    if(ans<0) ans+=mod;
    printf("%d\n",ans);
    return 0;
}
0%