用户:幻想乡的卡面来打/个人博客

因为不喜欢朋友圈所以打算挂这里.jpg

2023年

10月

5日

草，突然发现好多作业没写（

前段时间去了趟四川成都世界线漫展，大开眼界（

找到了几个卡面来打（

马上要走的时候甚至找到了车万coser（真稀有啊草

以及入手了三月精漫画（

正在打oi月赛完了我成采集了

---

打完了第三题没做出来

最后一题仅凭12行就切掉了

对付垃圾大数据量题的最好方法就是求助于数学www

题面

ps：这个T……是废的其实，因为所有的测试样例都是输入一组数据且因为没有输入结束标志不固定的输入组数在C++里不可能实现

这是真的（

因为数据量太多你用常规解法是会T L E的（

然后……

然后我找规律给它解出来了（

不遍历，不递归，纯找规律（

数学大法好！

解法

首先分析fib的规律，枚举可得

1 1 2 3 5 8 13 21

这玩意还用说吗……斐波那契

通过枚举可得

i=1->1种（111）

i=2->3

i=3->7

i=4->13

（右侧数为结果对998244353取余）

规律为

1

1+2*1

1+2*(1+2)

1+2*(1+2+3)

第n项就是

2*(1+n)*n/2+1

整理得 n²+n+1

所以第n项就是这个哒（

当然结果还没出来我也不知道对不对（

---

结果出来了，三个测试点全wa了（

可是本地都过了啊（