#P6358. 鬼故事 加强版
鬼故事 加强版
题目描述
给定 ,求:
其中 ,,。
作为良心(迫真)出题人,你只需要将答案对 取模。
输入格式
输入一行三个正整数 。
输出格式
输出一行一个整数,表示答案。
提示
【数据范围】
对于 的数据,;
对于 的数据,;
对于 的数据,,。
请注意常数优化。
由于 开到高精度范围也没什么意义,因此这里就改为 了。
给定 l,r,k,求:
i=l∑rj=i∏i+k−1fj其中 f0=0,f1=1,fn=fn−1+fn−2 (n≥2)。
作为良心(迫真)出题人,你只需要将答案对 998244353 取模。
输入一行三个正整数 l,r,k。
输出一行一个整数,表示答案。
【数据范围】
对于 30% 的数据,1≤k≤1000;
对于 70% 的数据,1≤k≤105;
对于 100% 的数据,1≤k≤5×105,1≤l≤r≤1018。
请注意常数优化。
由于 l,r 开到高精度范围也没什么意义,因此这里就改为 1018 了。