洛谷P3773 [CTSC2017]吉夫特(Lucas定理,dp)
2018-08-02 05:43:45来源:博客园 阅读 ()
题意
满足$b_1 < b_2 < \dots < b_k$且$a_{b_1} \geqslant a_{b_2} \geqslant \dots \geqslant a_{b_k}$
Sol
组合数取模?
肯定考虑Lucas定理
考虑Lucas定理在最后一步肯定会化为$C(1, 1), C(1, 0), C(0, 0), C(0, 1)$。
很显然$C(0,1)$不存在,而其他的都等于$1$,因此当最后分解为$C(0, 1)$的时候不满足条件。
具体怎么判断呢?观察上式可以得到一个普遍的规律:若$C(x, y) \{x = 0, 1 \ y=0,1 \}$,则$x\&y = y$
根据Lucas定理,显然我们可以把这个公式推广开来。
若$C(n,m)$为奇数,则$n \& m = m$
有了这个定理,我们就可以dp了。直接枚举子集就好。
时间复杂度:
枚举子集的复杂度是$O(3^n)$的,在此题中我们需要枚举二进制位,
因此复杂度为$3^{max log233333}$
#include<iostream> #define LL long long using namespace std; const int mod = 1000000007; LL f[233334], N, ans = 0; int main() { ios::sync_with_stdio(0); cin.tie(0); cin >> N; for(int i = 1; i <= N; i++) { int x; cin >> x; for(int j = x; j <= 233333; j = j + 1 | x) (f[x] += f[j]) %= mod; (ans += f[x]) %= mod; f[x]++; } cout << ans; return 0; }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash