You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有一个 $1..n$ 依次连成的环，有一个从 $1$ 开始移动的指针，每次指针所在位置有$p$的概率消失并将这个位置对应的下标（在 $1..n$ 中）插入序列 $B$ 的末尾，然后指针移动一格（ $1$ 移到 $2$，$n$ 移到 $1$ 这样，一个位置若已经消失则不会被移动到）。所有位置都消失时游戏结束。最后 $B$ 会是一个排列。

这道题跟序列 $B$ 没什么关系，你只需要求出游戏期望进行几轮，答案对 $998244353$ 取模。

输入格式

一行三个整数 $n,x,y$。概率 $p=\frac x y$。

输出格式

一行一个整数表示答案。

样例输入一

1 1 2

样例输出一

2

样例输入二

4 2 3

样例输出二

6

数据范围

对于$30\%$的数据，$n \leq 10$

对于$40\%$的数据，$n \leq 20$

对于$70\%$的数据，$n \leq 10^5$

对于所有数据，$1\leq n \leq 10^9, 0 < x < y < 998244353$

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#define int long long
using namespace std;
const int maxn=3e6+5;
int inv[maxn];
signed main()
{
    int n,p;
    cin>>n>>p;
    inv[1]=1;
    cout<<1<<endl;
    for(int i=2;i<=n;i++)
    inv[i]=p-(p/i)*inv[p%i]%p,
    printf("%lld\n",inv[i]);
    return 0;
}