Problem Statement
You are given a tuple of $N$ non-negative integers $A=(A_1,A_2,\ldots,A_N)$ such that $A_1=0$ and $A_N>0$.
Takahashi has $N$ counters. Initially, the values of all counters are $0$.
He will repeat the following operation until, for every $1\leq i\leq N$, the value of the $i$-th counter is at least $A_i$.
Choose one of the $N$ counters uniformly at random and set its value to $0$. (Each choice is independent of others.)
Increase the values of the other counters by $1$.
Print the expected value of the number of times Takahashi repeats the operation, modulo $998244353$ (see Notes).
Notes
It can be proved that the sought expected value is always finite and rational. Additionally, under the Constraints of this problem, when that value is represented as $\frac{P}{Q}$ using two coprime integers $P$ and $Q$, one can prove that there is a unique integer $R$ such that $R \times Q \equiv P\pmod{998244353}$ and $0 \leq R \lt 998244353$. Find this $R$.
Constraints
- $2\leq N\leq 2\times 10^5$
- $0=A_1\leq A_2\leq \cdots \leq A_N\leq 10^{18}$
- $A_N>0$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $A_1$ $A_2$ $\ldots$ $A_N$
Output
Print the expected value of the number of times Takahashi repeats the operation, modulo $998244353$.
Sample Input 1
2 0 2
Sample Output 1
6
Let $C_i$ denote the value of the $i$-th counter.
Here is one possible progression of the process.
- Set the value of the $1$-st counter to $0$, and then increase the value of the other counter by $1$. Now, $(C_1,C_2)=(0,1)$.
- Set the value of the $2$-nd counter to $0$, and then increase the value of the other counter by $1$. Now, $(C_1,C_2)=(1,0)$.
- Set the value of the $1$-st counter to $0$, and then increase the value of the other counter by $1$. Now, $(C_1,C_2)=(0,1)$.
- Set the value of the $1$-st counter to $0$, and then increase the value of the other counter by $1$. Now, $(C_1,C_2)=(0,2)$.
In this case, the operation is performed four times.
The probabilities that the process ends after exactly $1,2,3,4,5,\ldots$ operation(s) are $0,\frac{1}{4}, \frac{1}{8}, \frac{1}{8}, \frac{3}{32},\ldots$, respectively, so the sought expected value is $2\times\frac{1}{4}+3\times\frac{1}{8}+4\times\frac{1}{8}+5\times\frac{3}{32}+\dots=6$. Thus, $6$ should be printed.
Sample Input 2
5 0 1 3 10 1000000000000000000
Sample Output 2
874839568
概率生成函数做法，下面以 \('\) 表示求导
放几个求导公式先。
设最终的概率生成函数为 \(H(x)\)，\(H(x)=\frac{F(x)}{G(x)}\)，F表示 \(0\) 时刻 \(A\) 全为 0,在 \(i\) 时刻符合要求的概率，\(G\) 表示 \(0\) 时刻满足要求，在 \(i\) 时刻满足要求的概率。这是因为 \(G*H=F\)，很容易理解。根据生成函数的经典结论,\(H'(1)\) 为最终答案。
那么 \(F\) 和 \(G\) 是可以求出来的。先看 F，一种操作序列满足要求的前提是操作序列长度至少为 \(a_n\) 且最后 \(a_i\) 次操作没有弄 \(i\)。
我们需要知道如果从某个时刻开始形成 \(A_i\)，那么生成从出来的概率是多少。那么有 \(a_{i+1}-a_i\) 个时刻，生成出来的概率是 \(\frac in\)。那么定义 \(s_i=\prod_{j<i}(\frac jn)^{a_{j+1}-a_j}\)，可以用一个前缀积求出。 F 就是从任意大于 \(a_n\) 的时刻都有 \(s_i\) 的概率成功，\(F(x)=s_n(x_{a_n}+x_{a_n+1}+\cdots)=\frac{s_nx^n}{1-x}\)
那么 G 的生成函数呢？ G 和 F 的区别是他不一定需要 \(a_n\) 时刻才能满足，它可以只用 \(a_i\) 时刻，重构前面 \(i\) 个数。这里设时刻 \(a_i]\le j<a_{i+1}\)，那么 \(j\) 时刻开始的概率就是 \(s_i(\frac in)^{j-a_i}\)，用一个等比数列求和，这里省略一下过程，得到 \(g(x)=\frac{s_nx^{a_n}}{1-x}+\sum\limits_{i=1}^{n-1}n\frac{s_ix^{a_i}-s_{i+1}x^{a_{i+1}}}{n-ix}\)
然后求导，发现两个函数中 1 处的取值都是没有意义的，但是把 \(F\) 和 \(G\) 同乘 \((1-x)\)即可。后面的 F 和 G 都是乘了 \(1-x\) 之后的。\(F(1)=s_n,F'(1)=s_na_n,G(1)=s_n\)(后面的乘上 (1-x)) 后，带入 \(x=1\) 全部消掉。那么现在重点来推 \(G'(1)\)
现在要求 \(\frac{n(s_ix^{a_i}-s_{i+1}x^{a_{i+1}})(1-x)}{n-ix}\) 的导数，下面平方后出来 \((n-ix)^2=(n-i)^2\),方便起见，设 \((1-x)=A(x),s_{i}x^{a_i}-s_{i+1}x^{a_{i+1}}=B(x)\)，则 \((nA*B)'(1)=n(A'*B(1)+A*B'(1))\)，发现 \(A(1)=0\)，那么最终式子简化问 \(nA'*B(1)=-ns_{i}+ns_{i+1}\)。\(n-ix\) 求导为 \(-i\)，那么最终式子就是 \(\frac{n(s_{i+1}-s_i)(n-i)}{(n-i)^2}=\frac{n(s_{i+1}-s_i)}{n-i}\)
最后套除法求导公式就行了
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,P=998244353;
typedef long long LL;
int n,g,f,fp,gp,fd,s[N];
LL a[N];
int pown(int x,LL y)
{
if(!y)
return 1;
int t=pown(x,y>>1);
if(y&1)
return 1LL*t*t%P*x%P;
return 1LL*t*t%P;
}
int main()
{
scanf("%d",&n);
s[0]=s[1]=1;
for(int i=1;i<=n;i++)
{
scanf("%lld",a+i);
if(i^1)
s[i]=1LL*s[i-1]*pown((i-1LL)*pown(n,P-2)%P,a[i]-a[i-1])%P;
}
fp=s[n]*1LL*(a[n]%P)%P;
f=s[n];
g=s[n],gp=s[n]*1LL*(a[n]%P)%P;
for(int i=1;i<n;i++)
(gp+=pown(n-i,P-2)*1LL*n%P*(s[i+1]-s[i]+P)%P)%=P;
printf("%lld",(fp*1LL*g%P-gp*1LL*f%P+P)*pown(g*1LL*g%P,P-2)%P);
}