51NOD 2368 珂朵莉的旅行
2024-09-07 22:19:02
答案参考来自 http://www.cnblogs.com/sugewud/p/9822933.html
思路:思维题OR规律题?个人没写出来,脑子里只有深度DFS暴力,看完了一个大佬的题解,学到了思路ANDpow()函数的另一种写法,妙不可言!
先说思路:从一条链的时候开始推导,假如这条链长度为n,这条链上面的点分为两种—端点和非端点;
先看非端点的情况 0-0-0-0-0-0-0-0-0-0-0
其中的某一个非端点,到达两个端点的情况是2^(n-2),也就是说这个非端点到达一个端点的时,除去这个端点的的路上非端点的值01都行,最后到达端点时根据01的情况来确定端点值,所以端点值是确定的,那么到达两个端点的情况加起来就是2^(n-2)。
再来看端点的情况,0-0-0-0-0-0-0-0-0-0-0-0
只需考虑一个端点到达另一个端点,在该端点到达另外一个端点的路上,也就是说包含了一个端点和所有的非端点,这些端点值都是可以任意取值的,最后到达另一个端点时根据当前01的情况来考虑另一个端点的值,也就是说另一个端点的值其实是已经确定了的,这样的话情况就是2*2^(n-1)。
上面是两个端点的情况,以此类推到k个端点的情况,可以得到最后的答案是(n+k)*2^(n-k);
再来说一下pow()函数,直接上代码,我觉得很好需要保存一下
ll pow(ll a, int b)
{
ll res = % mod; a %= mod;
for(; b; b >>= )
{
if(b & ) res = res * a % mod;
a = a * a % mod;
}
return res;
}
以下是我写的题解(算不算我写的呢
最新文章
- TCP与UDP的区别
- Freemarker工具类
- eclipse安装hibernate
- 异常处理:Sys.WebForms.PageRequestManagerParserErrorException:The message……
- PHPCMS教程
- HDU 5430 Reflect
- work_8
- 03 javadoc
- TIMAC 学习笔记(三)
- php对mongo操作问题
- window.onload多个共存 - 借鉴jQuery.noConflict的思路
- LeetCode OJ 229. Majority Element II
- 深度学习(一)cross-entropy softmax overfitting regularization dropout
- druid 连接池加密算法
- Docker卸载高版本重装低版本后启动提示:driver not supported
- C# 对密码等数据进行对称性加密解密
- iOS开发CAAnimation详解
- [daily][tcpdump][bpf] 如何用tcpdump抓到一个分片包
- 对象的继承(__proto__和Object.setPrototypeOf(child,father))
- python3中SSLError错误处理
热门文章
- 正睿多校联盟训练Week6
- vue 相关技术文章集锦
- spring源代码下载并导入eclipse技巧
- 奇葩问题: lsattr -d /data 显示:----------I--e- /data/
- commons-lang常用工具类StringEscapeUtils使用--转
- ssm(Spring、Springmvc、Mybatis)实战之淘淘商城-第五天(非原创)
- 免费大数据搜索引擎 xunsearch 实践
- java urlEncode 和urlDecode的用法
- 10.3 Implementing pointers and objects and 10.4 Representing rooted trees
- Python学习 Day 4 函数 切片 迭代 列表生成式 生成器