洛谷3773 [CTSC2017]吉夫特

Luogu

BZOJ

分析

根据$\mathrm{Lucas}$定理,$C(n,m)\equiv C(n\%2,m\%2)\cdot C(n/2,m/2)\pmod 2$

显然只有$n\&m=n$时,$C(n,m)\%2$才能大于$0$。

设$f[i]$表示以$i$结尾的所有满足条件的最长不上升子序列的所求式子的和,可以直接$O(n^2)$转移。

优化一下,开个桶暴力记答案,就可以氵过去。

注意减掉长度为$1$的子序列。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int MAXN=500000+10;
const int MOD=1e9+7;

int a[MAXN],f[MAXN],s[MAXN];
int lg[MAXN];

int main() {
    int n=read(),mx=0,ans=0;
    for (re int i=1;i<=n;++i) a[i]=read(),mx=max(mx,a[i]);
    for (re int i=2;i<=mx;++i) lg[i]=lg[i>>1]+1;
    for (re int i=1;i<=n;++i) {
        int p=((1<<(lg[mx]+1))-1)^a[i];
        f[i]=1;
        for (re int S=p;S;S=(S-1)&p)
            f[i]=(f[i]+s[a[i]|S])%MOD;
        ans=(ans+f[i])%MOD,s[a[i]]=f[i];
    }
    printf("%d\n",ans-n); //减掉长度为1的子序列
    return 0;
}
最后修改:2019 年 09 月 24 日 08 : 30 PM

发表评论