【bzoj4903/uoj300】[CTSC2017]吉夫特 数论+状压dp
题目描述
给出一个长度为 $n$ 的序列,求所有长度大于等于2的子序列个数,满足:对于子序列中任意两个相邻的数 $a$ 和 $b$ ($a$ 在 $b$ 前面),${a\choose b}\mod 2\neq 0$。答案对 $10^9+7$取模。
输入
第一行一个整数 $n$ 。
接下来 $n$ 行,每行一个整数,这 $n$ 行中的第 $i$ 行,表示 $a_i$ 。
$1\le n\le 211985,1\le a_i\le 233333$
输出
一行一个整数表示答案。
样例输入
4
15
7
3
1
样例输出
11
题解
数论+状压dp
考虑Lucas定理求组合数的过程: ${n\choose m}\mod 2={{n\mod 2}\choose{m\mod 2}}·{{n/2}\choose{m/2}}\mod 2$
相当于 ${n\mod 2}\choose{m\mod 2}$ 是 $n$ 和 $m$ 的二进制最后一位,如果结果不等于0,则每一次递归的 ${n\mod 2}\choose{m\mod 2}$ 都不能等于0。
考虑实际意义,即不能存在二进制某一位,$n$ 的该位为0, $m$ 的该位为1。那么就相当于 $m$ 是 $n$ 的子集。
设 $f[i]$ 表示以数 $i$ 结尾的满足条件的子序列的数目,那么对于数 $j$ ,如果 ${i\choose j}\mod 2\neq 0$(即满足上面的子集性质),且 $j$ 出现的位置在 $i$ 后面 ,那么就可以从 $j$ 更新到 $i$ ,$f[i]+=f[j]+1$。
可以通过枚举子集的技巧 $j=i\ and\ (j-1)$,使得时间复杂度为 $O(3^{\log_2233333})=O(322137234)=O(能过)$
#include <cstdio>
#define mod 1000000007
int p[233334] , f[233334];
int main()
{
int n , i , j , x , ans = 0;
scanf("%d" , &n);
for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , p[x] = i;
for(i = 1 ; i <= 233333 ; i ++ )
if(p[i])
for(j = i & (i - 1) ; j ; j = i & (j - 1))
if(p[j] > p[i])
f[i] = (f[i] + f[j] + 1) % mod;
for(i = 1 ; i <= 233333 ; i ++ ) ans = (ans + f[i]) % mod;
printf("%d\n" , ans);
return 0;
}
最新文章
- 由用友NC刷新功能得到启示
- HDU2433 BFS最短路
- Replication的犄角旮旯(七)-- 一个DDL引发的血案(下)(聊聊logreader的延迟)
- Linux kernel的 Makefile和Kconfig以及Make menuconfig的关系【转】
- ptypes中string类的空间分配
- Spring与Struts2整合VS Spring与Spring MVC整合
- 编码神器 Sublime Text 包管理工具及扩展大全
- linux 进程监控和自动重启的简单实现
- gulp杂记
- Asp.net MVC 生成zip并下载
- Python学习最佳路线图
- animation 动画
- DDB---查询与优化
- SpringAOP深入学习
- UPDATE语句中SET部分列赋值的先后顺序有影响么?
- Python爬虫学习——光学字符识别
- django项目的生产环境部署,利用nginx+uwsgi
- 数组插件----linq.js
- Ruby(2): 基本语法上
- django中的template部分
热门文章
- SQL Server 中对 FOR XML和FROM的转换处理
- 北京Uber优步司机奖励政策(12月2日)
- 深圳Uber优步司机奖励政策(1月4日~1月10日)
- 全球订单最多的成都优步推出";南北通勤线";业务
- lunix安装
- Qt 计算两个日前间隔天数
- hadoop3.0新特性及新功能
- [leetcode-738-Monotone Increasing Digits]
- VBA基础之Excel 工作表(Sheet)的操作(二)
- vue.js学习之better-scroll封装的轮播图初始化失败