この解説では、 \(n\) 個のものから \(r\) 個取って並べる方法の数(順列) を \(_nP_r\) と表記します。

まず、ひとつ例を取り上げます。 \(N=6, K=4, P=(4,6,5,1)\) の場合を考えてみましょう。
手で数えようとしたとき、まず以下のものを取り扱うはずです。

• 辞書 \(s\) に含まれる、先頭が \(1\) である列
• 辞書 \(s\) に含まれる、先頭が \(2\) である列
• 辞書 \(s\) に含まれる、先頭が \(3\) である列

その次に取り扱うものは以下の通りであるはずです。

• 辞書 \(s\) に含まれる、接頭辞が \((4,1)\) である列
• 辞書 \(s\) に含まれる、接頭辞が \((4,2)\) である列
• 辞書 \(s\) に含まれる、接頭辞が \((4,3)\) である列
• 辞書 \(s\) に含まれる、接頭辞が \((4,5)\) である列

この直感に従いながらこの問題に正解することを考えます。

\(i = 1,2,\dots,K\) について以下の手順を行います。

• 辞書 \(s\) に含まれる、先頭 \(i-1\) 要素が \(P\) と一致し、 \(i\) 要素目が \(1\) 以上 \(P_i-1\) 以下であるような列を取り扱う。
  • \(P\) の先頭 \(i-1\) 要素に含まれない \(1\) 以上 \(P_i-1\) 以下の整数の個数を \(c\) とする。
  • \(1\) 以上 \(P_i-1\) 以下の整数であり \(P\) の先頭 \(i-1\) 要素に含まれないものについて、その全てが \(\displaystyle _{N-i}P_{K-i} + (c-1) \times _{N-i}P_{K-i} \times \frac{K-i}{N-i}\) 回出現する。
  • \(P_i\) 以上 \(N\) 以下の整数であり \(P\) の先頭 \(i-1\) 要素に含まれないものについて、その全てが \(\displaystyle c \times _{N-i}P_{K-i} \times \frac{K-i}{N-i}\) 回出現する。
  • (上記 \(2\) 式は \(N=K\) の場合ゼロ除算を含むので、必要に応じて適切に処理してください)
• \(i\) までの処理を終えた時点で \(P_i\) の総出現回数は 「この時点までで考慮したもの」 \(+\) 「これ以降に考える列の総数 \(\varDelta_i\) (= 辞書 \(s\) に含まれる列であって辞書順で \(P\) 以下のものであって、最初 \(i\) 項が \(P\) と一致するもの )」と確定する。

\(P\) に含まれない値の出現回数については、 \(i=K\) での処理を終えた時点で確定させることができます。

時間計算量を無視すれば、この時点でこの問題の求解はできています。

では、高速化を考えましょう。
気付くべきポイントは次の \(2\) 点です。

• \(\varDelta_i\) は \(i\) の降順に求めていくことで、全体で \(O(K \log N)\) で求めることができる。
• 「 \(1\) 以上 \(P_i-1\) 以下の整数であり \(P\) の先頭 \(i-1\) 要素に含まれないものについて、その全てが \(\alpha\) 回出現する」というような形の加算が発生するが、この加算以前の時点で「 \(P\) の先頭 \(i-1\) 要素に含まれるもの」については総出現回数が確定しているので、「 \(P\) の先頭 \(i-1\) 要素に含まれないものについて」を無視して単なる区間加算と見做して捌くことができる。

この高速化を適用するには、区間加算一点取得ができるデータ構造を用意しておく必要があります。(例えば、ACLの lazy_segtree を用いることが出来ます)

以上より、この問題に \(O(N \log N)\) といった時間計算量で正解できます。(問題が再帰で取り扱える構造をしていることからも察せるように、)全体の実装には再帰が便利です。
注意: 方針によっては再帰が \(3 \times 10^5\) 段にのぼるので、手元での実行の際には注意が必要である場合があります。このような場合、コードテストも便利です。

実装例(C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

#define mod 998244353
#define FACSIZE 1048576

long long power(long long a,long long b){
  long long x=1,y=a;
  while(b>0){
    if(b&1ll){
      x=(x*y)%mod;
    }
    y=(y*y)%mod;
    b>>=1;
  }
  return x%mod;
}

long long modular_inverse(long long n){
  return power(n,mod-2);
}

long long factorial[FACSIZE];
long long invfact[FACSIZE];

void cfact(){
  long long i;
  factorial[0]=1;
  factorial[1]=1;
  for(i=2;i<FACSIZE;i++){
    factorial[i]=factorial[i-1]*i;
    factorial[i]%=mod;
  }
  invfact[FACSIZE-1]=modular_inverse(factorial[FACSIZE-1]);
  for(i=FACSIZE-2;i>=0;i--){
    invfact[i]=invfact[i+1]*(i+1);
    invfact[i]%=mod;
  }
}

long long calcnCr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*((invfact[k]*invfact[n-k])%mod))%mod;
}

long long calcnPr(long long n,long long k){
  if(k<0 || n<k){return 0;}
  return (factorial[n]*invfact[n-k])%mod;
}

// https://betrue12.hateblo.jp/entry/2020/09/23/005940#%E5%8C%BA%E9%96%93%E5%8A%A0%E7%AE%97%E5%8C%BA%E9%96%93%E5%92%8C%E5%8F%96%E5%BE%97
struct S{
    long long value;
    long long size;
};
using F = long long;

S op(S a, S b){ return {(a.value+b.value)%mod, (a.size+b.size)%mod}; }
S e(){ return {0, 0}; }
S mapping(F f, S x){ return {(x.value + f*x.size)%mod, x.size}; }
F composition(F f, F g){ return (f+g)%mod; }
F id(){ return 0; }

long long n,k;
vector<long long> p;
vector<long long> res;
lazy_segtree<S, op, e, F, mapping, composition, id> seg;
lazy_segtree<S, op, e, F, mapping, composition, id> segpt;

long long rep(long long pos){
  if(pos==k){
    for(long long i=0;i<n;i++){
      if(segpt.get(i).value==1){
        res[i]=seg.get(i).value;
      }
    }
    return 1;
  }

  long long rank=segpt.prod(0,p[pos]).value;
  segpt.apply(p[pos],-1);

  long long unit=calcnPr(n-pos-1,k-pos-1);
  long long exist=(((unit*(k-pos-1))%mod)*modular_inverse(n-pos-1))%mod;
  long long smaller,larger;

  // actually, this case work isn't required
  if(pos==k-1){
    smaller=1;
    larger=0;
  }
  else{
    smaller=((exist*(rank-1))+unit)%mod;
    larger=(exist*rank)%mod;
  }

  seg.apply(0,p[pos],smaller);
  seg.apply(p[pos],n,larger);

  res[p[pos]]=seg.get(p[pos]).value;
  long long upper=(rank*unit)%mod;
  long long lower=rep(pos+1);
  res[p[pos]]+=lower;
  res[p[pos]]%=mod;
  return (upper+lower)%mod;
}

int main(){
  cfact();
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n >> k;
  p.resize(k);
  for(auto &nx : p){
    cin >> nx;
    nx--;
  }
  res.resize(n);

  vector<S> ini(n,{0,1});
  lazy_segtree<S, op, e, F, mapping, composition, id> inis(ini);
  seg=inis;
  segpt=inis;
  segpt.apply(0,n,1);

  rep(0);

  for(auto &nx : res){
    cout << nx%mod << "\n";
  }
  return 0;
}