menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[DP]UOJ300(CTSC2017)【吉夫特】题解
apps UOJ
local_offer 查看标签
comment 0 条评论

题目概述

求不上升OrzJZ子序列的个数,OrzJZ子序列需要满足 $\prod_{i=2}^{k}{a_{i-1}\choose a_i}\ mod\ 2=1$ 。

解题报告

因为一个 $0$ 都不能出现,根据Lucas定理,子序列必须前一项 $and$ 后一项 $=$ 后一项才能满足这个要求。那么我们就可以直接枚举子集来搞……题目里又有神助攻“没有相同的”,所以效率就是 $O(3^{log_2a_{max}})$ 。

示例程序

#include<cstdio>
using namespace std;
const int maxn=211985,maxa=262144,MOD=1e9+7;

int n,pos[maxa],f[maxa],ans;

inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
int main(){
    freopen("program.in","r",stdin);
    freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1,x;i<=n;i++) scanf("%d",&x),pos[x]=i,f[x]=1;
    for (int i=1;i<maxa;i++)
        for (int j=pos[i]?i&i-1:0;j;j=i&j-1)
            if (pos[j]>pos[i]) AMOD(f[i],f[j]);
    for (int i=1;i<maxa;i++) if (pos[i]) AMOD(ans,f[i]-1);
    return printf("%d\n",ans),0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTex数学公式
sentiment_very_satisfied
keyboard_arrow_up