2019牛客国庆集训派对day2 J.Vertex Cover(思维,组合数学算贡献)
发布日期:2021-06-30 10:32:59
浏览次数:3
分类:技术文章
本文共 1049 字,大约阅读时间需要 3 分钟。
从序号最大的点开始考虑
考虑 ( i , j ) (i,j) (i,j)(其中 i < j i<j i<j)这条边,选和不选的方案数放在 i i i点考虑
这样可以做到不重不漏
设 p p p表示权值大于 i i i且被选择的点数, q q q表示权值大于 i i i且没被选择的点数
①.若点 i i i被选择(只考虑 ( i , j ) (i,j) (i,j)边,其中 i < j i<j i<j)
那么至少存在一个代价更大且没被选择的点和 i i i相连
如果不是这样,完全可以不选 i i i而把其他小于 i i i的点全选上,更优
如果是这样,那么可以保证 i i i会被选择
方案数是 ( 2 q − 1 ) ∗ 2 p (2^{q}-1)*2^p (2q−1)∗2p
②.若点 i i i没有被选择(只考虑 ( i , j ) (i,j) (i,j)边,其中 i < j i<j i<j)
显然 i i i不可能和其他代价更大且没有被选择的点相连
显然 i i i可能和所有代价更大且被选择的点相连
这样最优,方案数是 2 q 2^q 2q
累乘即是答案
#includeusing namespace std;#define int long longconst int maxn = 1e6+10;const int mod = 1e9+7;int base[maxn],n;char a[maxn];signed main(){ base[0] = 1; for(int i=1;i<=1000000;i++) base[i] = base[i-1]*2%mod; while( cin >> n >> ( a+1 ) ) { int p = 0 , q = 0 , ans = 1;//被选择的点,没有被选择的点 reverse( a+1,a+1+strlen(a+1) ); for(int i=strlen(a+1)+1;i<=n;i++) a[i] = '0'; for(int i=n;i>=1;i--) { if( a[i]=='0' )//不被选择 ans = ans*base[p]%mod,q++; else ans = ans*( base[q]-1 )%mod*base[p]%mod,p++; } cout << (ans%mod+mod)%mod << endl; }}
转载地址:https://issue-is-vegetable.blog.csdn.net/article/details/116542170 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
留言是一种美德,欢迎回访!
[***.207.175.100]2024年04月14日 08时06分51秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
优化页面请求性能——防抖
2019-04-30
优化网络请求性能——节流
2019-04-30
javascript 之 模拟new关键字的功能
2019-04-30
JavaScript深入之call和apply的模拟实现
2019-04-30
javaScript手撕代码之leetcode-最大正方形
2019-04-30
Vue之单向数据流
2019-04-30
ES6之深入Set 与 WeakSet的知识讲解
2019-04-30
算法之链表的逆转
2019-04-30
Set 和 Array 玩转 交/并/差集
2019-04-30
javaScript之事件模型,你知道多少?
2019-04-30
Vue2.0:双向数据绑定 之 监听对象,源码分析
2019-04-30
浅析:正则表达式修改字符串数字“10000”为“10,000”
2019-04-30
浅析chrome新特性,追溯源头至HSTS
2019-04-30
记一次曲折的Debug经历
2019-04-30
Impala支持Google云存储开发笔记
2019-04-30
如何在Apache JIRA中搜索issue
2019-04-30
Impala-shell相关源码笔记
2019-04-30
Windows下配置Storm源码阅读环境(vim+ctags)
2019-04-30
Storm源码细读——Nimbus启动
2019-04-30
Storm源码细读——Supervisor启动
2019-04-30