UOJ300【CTSC2017】吉夫特 <子集DP>

Problem

【CTSC2017】吉夫特

时间限制：$\mathrm{2\;Sec}$
空间限制：$\mathrm{256\;MB}$
简单的题目，既是礼物，也是毒药。
$\mathrm{B君}$设计了一道简单的题目，准备作为 $\mathrm{gift}$ 送给大家。
输入一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$
问有多少个长度大于等于 2 的不上升的子序列 $a_{b_1}, a_{b_2}, \ldots ,a_{b_k}$ 满足
$\prod_{i = 2}^k \binom{a_{b_{i-1}}}{a_{b_i}} \bmod 2= \binom{a_{b_1}}{a_{b_2}} \times \binom{a_{b_2}}{a_{b_3}} \times \cdots \times \binom{a_{b_{k-1}}}{a_{b_k}} \bmod 2 > 0$
输出这个个数对 $1000000007$ 取模的结果。

输入格式

第一行一个整数 $n$。
接下来 $n$ 行，每行一个整数，这 $n$ 行中的第 $i$ 行，表示 $a_i$。

输出格式

一行一个整数表示答案。

样例输入输出

样例一

Input

4
15
7
3
1

Output

11

样例二至样例九

见样例数据下载。

限制与约定

对于前 $10\%$ 的测试点，$n \leq 9, 1 \leq a_i \leq 13$；
对于前 $20\%$ 的测试点，$n \leq 17, 1 \leq a_i \leq 20$；
对于前 $40\%$ 的测试点，$n \leq 1911, 1 \leq a_i \leq 4000$；
对于前 $70\%$ 的测试点，$n \leq 2017$；
对于前 $85\%$ 的测试点，$n \leq 100084$；
对于 $100\%$ 的测试点， $1 \leq n \leq 211985, 1 \leq a_i \leq 233333$。
所有的 $a_i$ 互不相同，也就是说不存在 $i,j$ 同时满足 $1 \leq i < j \leq n$ 和 $a_i=a_j$。

下载

样例数据下载

标签：子集DP

Solution

由$\mathrm{Lucas}$定理可以推得$\binom{n}{m}\equiv1\bmod{2}$当且仅当$n\&m=m$，于是原题转为需要使$a_{b_i}\&a_{b_{i+1}}=a_{b_{i+1}}$，即$a_{b_i}$是$a_{b_{i+1}}$的子集。
显然有$\mathrm{DP}$：令$f[i]$表示在$a_i$后面接若干个$a$满足条件的序列总数，那么对于$a$值是当前$a_i$的子集的所有位置$j$，均有$f[j]=f[j]+f[i]$。直接做子集$\mathrm{DP}$即可。

Code

#include <bits/stdc++.h>
#define MAX_A 233333
#define P 1000000007
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, s, f[MAX_A+5];
int main() {
    read(n);
    for (int i = 1, x, t; i <= n; i++) {
        read(x), t = (f[x]+1)%P, (s += t) %= P;
        for (int y = x; y; y = (y-1)&x)
            (f[y] += t) %= P;
    }
    return printf("%d\n", s-n), 0;
}