#P6873. 撸起袖子

    ID: 6704 传统题 1000ms 888MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-类欧几里得算法二项式定理自然数幂和公式交换求和顺序

撸起袖子

题目描述

一个圆形轮子沿顺时针依次刻有 0,1,…,c0,1,\ldots,c。指针初始指向 bb,初始任期为 bkb^k 年。每次任期结束后,转动轮子一次,使指针沿顺时针移动 aa 格。若新指向 xx,就再连任 xkx^k 年。

求第 n+1n+1 次转轮之前的总任期。总任期包含初始任期以及前 nn 次转轮后产生的任期。答案对 998244353998244353 取模。

输入格式

一行五个整数 n,a,b,c,kn,a,b,c,k。

输出格式

一行一个整数,表示总任期对 998244353998244353 取模后的结果。

样例

4 3 0 4 2
30

指针依次指向 0,3,1,4,20,3,1,4,2,对应任期为 0,9,1,16,40,9,1,16,4 年。

数据范围

0≤n,a,c<9982443530\le n,a,c<998244353,0≤b≤c0\le b\le c,1≤k≤1201\le k\le120。

原赛子任务 特殊限制 原赛分值
1 c≤106c\le10^6 1
2 k=1k=1 9
3 k≤10k\le10 20
4 无 70

原 PDF 题面