[luogu4834]萨塔尼亚的期末考试

2018-08-05

lolifamily

这里有 oeis 的解释，但是我看不懂。

题目大意：快速地求

$a n s = \sum 𝑛 𝑖 = 1 (𝑖 \cdot f i b (𝑖)) 𝑛 (𝑛 + 1) 2$

∵ 𝑛 \sum 𝑖 = 1 f i b (𝑖) = 1 + f i b (1) + f i b (2) + \dots + f i b (𝑛) - 1 [1 + (- 1) = = 0] = (f i b (2) + f i b (1)) + f i b (3) + \dots + f i b (𝑛) - 1 [f i b (1) = = f i b (2)] = (f i b (3) + f i b (2)) + f i b (4) + \dots + f i b (𝑛) - 1 [f i b (1) + f i b (2) = = f i b (3)] = \dots = f i b (𝑛 + 2) - 1 ∴ 𝑛 \sum 𝑖 = 1 𝑖 \cdot f i b (𝑖) = 𝑛 𝑛 \sum 𝑖 = 1 f i b (𝑖) - 𝑛 - 1 \sum 𝑖 = 1 𝑖 \sum 𝑗 = 1 f i b (𝑗) = 𝑛 (f i b (𝑛 + 2) - 1) - 𝑛 - 1 \sum 𝑖 = 1 (f i b (𝑖 + 2) - 1) = 𝑛 \cdot f i b (𝑛 + 2) - 𝑛 - (𝑛 - 1 \sum 𝑖 = 1 f i b (𝑖 + 2)) + (𝑛 - 1) = 𝑛 \cdot f i b (𝑛 + 2) - (𝑛 + 1 \sum 𝑖 = 1 f i b (𝑖) - 2) - 1 = 𝑛 \cdot f i b (𝑛 + 2) - (f i b (𝑛 + 3) - 1 - 2) - 1 = 𝑛 \cdot f i b (𝑛 + 2) - f i b (𝑛 + 3) + 2

写一个矩阵快速幂就可以解决问题，时间复杂度 $𝑂 (𝑇 \cdot l o g 2 (𝑛))$ ，但是不出意料的 T 掉了

观察一下结果，可以发现我们分别对 ans 中两个相邻的 fib 值进行计算，这并没有利用好矩阵乘法的性质

回想一下最初学习矩阵快速幂的时候，老师演算 fib 的时候是一个 $1 \times 2$ 的矩阵乘上 $2 \times 2$ 的矩阵，像这样：

[f i b (𝑛) f i b (𝑛 - 1)] [1110] = [f i b (𝑛 - 1) f i b (𝑛 - 2)]

我们用老师最初讲的方法来计算 fib 的值，可以节省一半的时间，在加上 $2 \times 2$ 的矩阵乘法不用 for 循环，就可以轻松切过这道题了～

UPD: 老师最后写的方法并不是错的，在只求一次或者不相邻的项中会显得更快一些，但这并不代表我们可以忘掉原来讲的那种方法（这真的是一道好题）

最终的矩阵为：

[10] [1110] 𝑛 + 3

题目背景

“呐，珈百璃，我说，暑假我们去哪里玩呢？“薇奈特拍拍珈百璃的肩膀

“哈？暑假当然是在家里打游戏啦” 珈百璃无精打采地回答道

“怎么能这样呢？你好歹也是天使啊，给我拿出天使的样子来啊”

“真麻烦”

“所以，暑假我们去海边玩吧？”

“赞成赞成！去海边玩的话，就可以好好调戏珈百璃了。“菈菲尔不知道什么时候凑进来

“麻烦死了。”

这边一群人正讨论着暑假去哪玩，然而萨塔尼亚在旁边听得很纠结，因为没有人邀请她……

“哼哼哼哼，吾乃神魔萨塔尼亚，怎么可能主动去加入呢，我必须等她们邀请我” 萨塔尼亚心理打着小算盘

“呐，我说，萨塔尼亚貌似有点小不开心呀”

“已经不是貌似了吧，她这表情完全没有掩盖的意思啊……”

“呐，我说，要不要邀请她去啊？”

拉菲尓说着，走向了萨塔尼亚。“萨塔尼亚桑，暑假我们要去海边玩哟～”

“哼哼哼，终于来邀请我了吗” 萨塔尼亚心里有点小开心，小声嘀咕道

“萨塔尼亚桑就好好待在这里哟～”

“额……” 萨塔尼亚受到了成吨的暴击，“喂，我说，哪有你这样的啊”

“恩？因为，萨塔尼亚桑，暑假如果要出去玩的话，就要通过期末考试哟，不然会被留下来补课的”

“补…… 补课……” 萨塔尼亚貌似意会到了什么，脸色大变，“补课…… 呐，拉菲尓…… 你…… 你能帮我…… 补习吗？”

“恩？可以呀～但是期末考试如何就得看你自己了”

“谢谢，那帮我看看这些哪里错了吧？我完全不懂诶”

“我看看……” 拉菲尓丢下珈百璃和薇奈特独自给萨塔尼亚开始了补习。

终于，期末考来了，萨塔尼亚努力的这么久，就看这次考试了！经过长期的努力，期末考一切顺利，除了还没考的数学其他学科都及格啦！

终于到了最后一场考试 —— 物理考试。很不错的是，萨塔尼亚已经答完了 59 分而且全对，但是她遇到了一道绝世难题，而且她很惊奇的发现，总分 100 分，这题 41 分，如果不写出来，就会挂科。

“期末考如果有某人有挂科，那么那个人的暑假要参加补课以及补考！“班主任的话萦绕在她的耳旁，这可怎么办啊……

题目描述

有一个由 $𝑛$ 个点电荷形成的电场，我们假定每个点电荷放出的电场都是匀强电场而不是点电荷电场，第 $𝑖$ 个点电荷的电场强度 $𝐸 𝑖 = 𝑖$ ，现放一个带负电的试探电荷到这个电场中，这个试探电荷只要触碰到任何一个点电荷就会和这个点电荷发生聚变放出巨大能量，因为点电荷放出的电场强度不同，所以试探电荷被吸引到每个点电荷的概率也不同，点电荷给试探电荷的吸引力越大被吸到这个点电荷的概率就越大，且成正比，我们假设最小的点电荷给试探电荷的吸引力为 $𝐹$ ，那么对于其他点电荷给试探电荷和吸引力就是 $𝑖 \cdot 𝐹$ ，那么假设触碰最小的点电荷的概率为 $𝑃$ ，则每个点的概率就是 $𝑖 \cdot 𝑃$ ，触碰到点电荷后发出的能量为 $f i b (𝐸 \cdot 𝑖)$ ，求期望放出的能量

好消息是，只要这道题拿到分，萨塔尼亚就能及格啦！

输入格式

第一行一个整数 $𝑇$ ，表示 $𝑇$ 组测试数据

接下来 $𝑇$ 行每行一个整数 $𝑛$ ，表示有 $𝑛$ 个点电荷

输出格式

对于每次询问输出一行一个整数表示期望能量，为了避免精度问题，我们输出的数都是 $m o d 998244353$ 下的

输入样例

输出样例

1
1

说明

样例解释： $13 \cdot f i b (1) + 23 \cdot f i b (2) = 1$

请结合样例仔细再仔细的读题！

对于 $10 %$ 的数据， $𝑇 = 1$ ， $𝑛 = 2$

对于 $30 %$ 的数据， $𝑇 \leq 10$ ， $𝑛 \leq 106$

对于 $60 %$ 的数据， $𝑇 \leq 106$ ， $𝑛 \leq 106$

对于 $100 %$ 的数据， $𝑇 \leq 106$ ， $𝑛 \leq 109$

$f i b (𝑖)$ 为斐波那契数列， $f i b (1) = f i b (2) = 1$ ， $f i b (𝑛) = f i b (𝑛 - 2) + f i b (𝑛 - 1)$ ( $𝑛 \geq 3$ )

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define LL long long
6
#define mod 998244353
7
using namespace std;
8
inline LL quickpow(LL a,LL b)
9
{
10
  LL ans=1;
11
  while(b)
12
  {
13
    if(b&1)ans=(ans*a)%mod;
14
    a=(a*a)%mod;b>>=1;
15
  }
16
  return ans;
17
}
18
int main(void)
19
{
20
  int n;
21
  scanf("%d",&n);
22
  ;
23
  return 0;
24
}