在遥远的提瓦特大陆，弥哈尤部落正准备发动一场决定生死存亡的远征。为了赢得这场战争，大先知决定举行一场古老的献祭仪式，以祈求元神的祝福。

按照传统习俗，部落需要在出征前从军队中挑选一名士兵进行献祭。作为部落的首席军事策略家，需要评估献祭每一名士兵后对军队整体力量的影响，以便大先知能做出最明智的决策。

题目

题目描述

部落拥有一支由 $n$ 名士兵组成的军队。第 $i$ 名士兵的力量值为 $a_i$。一支军队的总力量定义为其中所有士兵力量值的乘积。

请计算，对于从 $1$ 到 $n$ 的每一名士兵 $i$，依次计算当其被献祭后，由剩余 $n-1$ 名士兵组成的军队的总力量。

由于计算结果可能很大，所有计算出的总力量都需要对 $998244353$ 取模。

输入格式

输入共两行。

第一行输入一个整数 $n\ (2\le n\le{10}^7)$，代表士兵的数量。

第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n\ (0\le a_i\le100)$，代表每名士兵的力量值。

输出格式

输出共一行，包含 $n$ 个整数，以空格分隔。

第 $i$ 个整数表示献祭第 $i$ 名士兵后，军队中剩余士兵的总力量对 $998244353$ 取模的结果。

这道题是怎么来的

此题是我在网上冲浪时在 Google面试题中的两道趣题 | Matrix67: The Aha Moments 中看到的。题目如下：

给定长度为 $n$ 的序列 $a$，在 $O(n)$ 的时间内构造一个长度为 $n$ 的序列 $b$，使得

$b_i=\dfrac{1}{a_i}\prod\limits_{k=1}^n a_i$

当时就在思考是否能将此题变成一道算法竞赛题，最终也是成功改编成了今年新生赛的某道题目。

以下是我的思考历程：

很显然本题有一个 $O(n^2)$ 的做法，就是使用 $O(n)$ 的时间计算 $b_i$，可以通过增大 $n$ 的范围来轻松卡掉这个方法。

那既然增大了 $n$ 的范围，很显然会有 $b_i$ 溢出的可能性，故将题面改为求

$b_i={\left(\dfrac{1}{a_i}\prod\limits_{k=1}^n a_i\right)}\bmod M$

其中 $M$ 可以将输出结果限制在可控的 int 或 long long 范围内。除此之外，这还有一个优点，就是选手不能直接使用除法了，因为在计算 ${\left(\prod\limits_{k=1}^n {\left(a_i\bmod M\right)}\right)}\bmod M$ 后不能再执行除法，其中包含的因子被模掉了，直接应用除法会出现浮点数。

对于老道有经验的选手而言，它们会使用模意义下的除法来解决该问题，这也是对于他们而言最方便直接的做法。

在这里给新手解释一下什么是逆元：

首先回想小学学习的除法，我们是从倒数开始学习，将 $\dfrac ba$ 看成 $b\cdot\dfrac 1a$，其中 $\dfrac 1a$ 就是满足 $ax=1$ 的数字 $x$。

那么在模意义下也是类似的，设满足

$ax\equiv1\pmod p$

的 $x\ (0<x<p)$ 称为 $a$ 在模 $p$ 下的逆元，也可以认为是

$x\equiv \dfrac1a \pmod p$

可以想一想，为什么只有 $a$ 和 $p$ 互质时才有逆元，且这个逆元是唯一的。

模意义下的除法实际上就是将式子乘上除数的逆元。

故此题目前还可以使用费马小定理搭配快速幂，或者使用拓展欧几里得算法在 $O(\log a)$ 的时间复杂度中算出每个数 $a_i$ 的逆元，对于每个数都进行如此操作的总时间复杂度为 $O(n\log a)$。

故我仍然想尝试将 $n$ 和 $a$ 的范围拓展到 ${10}^7$ 和 ${10}^9$，但是由于此量级下 C/C++ 和其它编程语言的速度优劣势会拉开差距，并且即便在 C++ 中关闭输入输出流同步，所有数据读入的时间也远超 1s。

除此之外，即便能卡掉 $O(n\log a)$ 的做法，也有一个经典的方法可以在 $O(n)$ 求出 $n$ 个数字的逆元，所以使用逆元的方法可以将此题优化到 $O(n)$。

所以当时我只优化到了这步，便端上新生赛中给各位大一同学品尝。于是就有了上文中的题面。

正解

此题正解为前缀后缀积，可以在 $O(n)$ 的时间内预处理

$\begin{aligned} p_i&={\left(\prod\limits_{k=1}^ia_i\right)}\bmod M \\ s_i&={\left(\prod\limits_{k=i}^na_i\right)}\bmod M \\ \end{aligned}$

那么输出 ${(p_{i-1}s_{i+1})}\bmod M$ 即可，这个过程同样是 $O(n)$ 的，注意判断边界条件。

代码如下（略去了代码模板）：

const ll mod=998244353;
void test(){
    ll n;cin>>n;
    vll a(n),p(n),s(n);
    fe(u,a)cin>>u;
    auto e=[&](ll x,ll y){return x*y%mod;};
    partial_sum(all(a),p.begin(),e);
    partial_sum(rall(a),s.rbegin(),e);
    f(i,0,n){
        ll l=(i==0)?1:p[i-1];
        ll r=(i==n-1)?1:s[i+1];
        cout<<l*r%mod<<" ";
    }
    cout<<endl;
    return;
}

还能再升级吗

在新生赛进行到一半的过程中，我突然想到模逆元其实就是建立在互质的基础上的，所以说可以将模数改成 $998224353$ 或 $988244353$ 来混淆选手（这两个都是合数），或者要求输入自定的模数。

碎碎念

赛后发现还是有两名同学用正解方法求出本题，令人欣慰...