A simple Blog for wyx I've been down the bottle hoping.
4903: [Ctsc2017]吉夫特 枚举子集 DP Lucas
发表于: | 分类: Oi | 评论:0 | 阅读:63

考试的时候结论都想到了然后分治FWT也想到了最后没想到小范围暴力GG

交BZOJ被卡常应该就我一个了吧……

然后把分治FWT那个傻*算法扔到垃圾桶……

注意到$\mod 2$ 意义下 $C_n^m = 1$ 当且仅当 n&m==n

证明的话你可以这样,你用那个二进制的转移方式就看出来了,显然不能是上面是1下面是0,在其他情况都是n&m==n

注意到每个数字只出现一次,我们把对应的答案扔到权值的桶里面就行了……

然后每次就是枚举$x$的子集,复杂度是$3^{\log_2{val}}$

最后算出来近似可看成是$n^{1.44}$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 3e5+5;
const int M = 233333+5;
const int mod = 1000000007;

__attribute__((always_inline)) char getc()
{
    static const int LEN = 1<<15;
    static char buf[LEN],*S=buf,*T=buf;
    if(S == T)
    {
        T = (S=buf)+fread(buf,1,LEN,stdin);
        if(S == T)return EOF;
    }
    return *S++;
}

__attribute__((always_inline)) int read()
{
    static char ch;
    static int D;
    while(!isdigit(ch=getc())) if(ch == EOF) return -1;
    for(D=ch-'0'; isdigit(ch=getc());) D=(D<<3)+(D<<1)+(ch-'0');
    return D;
}
int a[N];
int T[M+5];

int main() {
    int n = read();
    for(int i=1;i<=n;++i) a[i] = read();
    reverse(a+1, a+n+1);
    register int j;
    for(int i=1;i<=n;++i) {
        int ans = 0;
        for(j=a[i];j;j=(j-1)&a[i]) {
            (ans += T[j]) %= mod; 
        }
        T[a[i]] = ans + 1;
    }
    long long ans = 0;
    for(int i=1;i<=n;++i) (ans += (T[a[i]] - 1) ) %= mod;
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP