CodeForces 1737 E - Ela Goes Hiking 题解
创始人
2025-05-31 19:03:04
0

思路

我们先将题目看成 nnn 个点的问题。

首先我们知道,如果一个点初始方向是向右,那么他无论如何都不可能活到最后。

所以我们只需要考虑向左的情况。

我们可以求出它初始方向向左时活到最后的方案数,然后除于所有的方案,就是我们要求的概率了,接下来我们考虑如何求出活到最后的方案数。

我们可以将整个过程分为两部分,首先向左走到底,此时右边的无论如何变化都不会影响到当前左边的部分,然后再转向向右。

设当前点为 iii,对于左边的部分,如果有一个点的编号大于 ⌊i2⌋\lfloor\frac{i}{2}\rfloor⌊2i​⌋ 并且它的初始方向向右,则当前节点一定会被这个节点吃掉。

所以编号大于 ⌊i2⌋\lfloor\frac{i}{2}\rfloor⌊2i​⌋ 的点的初始方向都要向右,所以左边一共有 2⌊i2⌋2^{\lfloor\frac{i}{2}\rfloor}2⌊2i​⌋ 种方案。

再考虑右边的部分,我们设当前的方案数为 fif_ifi​(不考虑左边的部分),则如果对于所有小于 2⋅i2\cdot i2⋅i 的点的方向全部向右,则说明当前节点一定会被吃掉(如果最后一个点向右,那么在吞掉别人之前一定会碰到墙回头,所以可以看成向左),为了防止当前节点被吃掉,则无论如何在小于 2⋅i2\cdot i2⋅i 的节点中有向左的,我们便可以写出关于 fif_ifi​ 的式子:

fi=∑j=i+12⋅ifjf_i = \sum_{j=i+1}^{2\cdot i} f_j fi​=j=i+1∑2⋅i​fj​

可以用前缀和优化到 O(n)O(n)O(n) 的时间复杂度。

然后将左边和右边的方案数乘起来,在除于所有的方案数,就是答案了。

代码

#include 
using namespace std;
typedef long long LL;
const LL MOD = 1e9 + 7;
int T, n;
LL f[3000005], g[3000005];
LL Pow(LL a, LL b) {LL s = 1;while (b) {if (b & 1)s = s * a % MOD;a = a * a % MOD, b = b >> 1;}return s;
}
int main() {scanf("%d", &T);while (T--) {scanf("%d", &n);for (int i = 1; i <= 2 * n; i++)f[i] = g[i] = 0;f[n] = g[n] = 1;for (int i = n - 1; i; i--)f[i] = (g[i + 1] - g[i * 2] + MOD) % MOD, g[i] = (g[i + 1] + f[i]) % MOD;for (int i = 1; i <= n; i++)printf("%lld\n", f[i] * Pow(2, i / 2) % MOD * Pow(Pow(2, n - 1), MOD - 2) % MOD);}return 0;
}

相关内容

热门资讯

布局低空,布局引领全球的万亿赛... 当前新质生产力相关的产业已成为最引人注目成长赛道,在众多新质生产力产业中,低空经济是少有的由我国引领...
特斯拉超级充电站餐厅开业,马斯... IT之家 7 月 22 日消息,特斯拉超级充电站餐厅(Supercharger Diner)今日在洛...
算力需求持续火热,人工智能ET... 截至2025年7月22日收盘,中证人工智能产业指数(931071)下跌0.82%。成分股方面涨跌互现...
一图解码:港股IPO一周回顾 ... 过去一周(2025.7.14-7.20),港股IPO市场共有3家公司递交了上市申请,分别为麦济生物、...
最强赛道,呈两极分化!有的猛增... 创新药赛道行情爆火的同时,医药基金的“留人能力”却呈现两极分化。 券商中国记者注意到,根据最新披露的...
菲律宾要失望了,知情人士:美国... 本月初,美国总统特朗普公布多国关税税率,其中,对菲律宾产品征收的“对等关税”从今年4月公布的17%升...
2025年广东省乡村旅游消费趋... 2024年,广东省乡村旅游接待游客5.1亿人次,占全省总旅游接待人次的58.6%;乡村旅游收入达37...
高晓峰:趋势线守卫战告捷 黄金... 来源:市场资讯 7月22日,国际黄金本周初受美元走软及贸易局势影响强势走高。美国通胀数据低于预期,黄...
原创 美... 在我们的日常生活中,电力早已融入了方方面面。我们习惯了出门时确保手机电量充足,家里需要WiFi的连接...
复牌“摘帽”!基金公司第一时间... 【导读】复牌当天再遭基金公司“补刀”,招商基金下调诺泰生物估值 中国基金报记者 若晖 因涉及财务造假...
24年老将、前公募总经理“奔私... 【导读】携手老同事创业,原公募总经理宋小龙备案上海理泉私募基金 中国基金报记者 吴君 又见公募基金总...
科创板开市6周年:已拥有589... 7月22日,科创板迎来开市6周年。这个中国资本市场最年轻的板块已经拥有589家上市公司、超7万亿元总...
科创板六周年!上市公司“掌门人... 【导读】 2025年7月22日,中国资本市场这片热土上,一块名为“科创板”的“试验田”已悄然耕耘六载...
聚焦"稳"... 北京2025年7月22日-- 当前,中国经济正经历深刻转型升级,企业面临市场波动、竞争加剧等多重挑战...
华泰柏瑞港股通时代机遇混合A:... AI基金华泰柏瑞港股通时代机遇混合A(011355)披露2025年二季报,第二季度基金利润292.6...
致179人遇难!韩国12·29... 据韩国《韩民族日报》7月21日报道,韩国国土交通部下属的“航空铁路事故调查委员会”7月19日就去年1...
卧龙电驱:7月21日融券卖出6... 证券之星消息,7月21日,卧龙电驱(600580)融资买入4.49亿元,融资偿还5.59亿元,融资净...
破解堵点卡点,做强国内大循环 国务院常务会议7月16日召开,研究做强国内大循环重点政策举措落实工作,并作出一系列针对性部署。会议指...