Submission #33929839

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
using mint=atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back

ll read(){ll r;scanf("%lld",&r);return r;} // read

const int N = 200000;

ll a[N+10];
mint fac[2*N+10] = {1}; // fac[i] = i!
mint ifac[2*N+10]; // ifac[i] = 1/i!
vector<mint> polys[N+10]; // 总长 <= O(n + k)
int idxs[N+10];

mint C(int n,int m){return fac[n]*ifac[m]*ifac[n-m];}

ll n; // 2e5
ll m; // 2e5
ll k; // 2e5

// 本质就是 尽量小乘小, 大乘大, 不要大量 大*小
vector<mint> solve(ll l,ll r) {
  if(l == r) return polys[idxs[l]];
  auto res = atcoder::convolution(solve(l,(l+r)/2),solve((l+r)/2+1,r));
  if((int)res.size() > m-k+1) res.resize(m-k+1);
  return res;
}

int main() {
  rep(i,1,2*N+1) fac[i] = fac[i-1]*i;
  ifac[2*N] = fac[2*N].inv();
  per(i,0,2*N) ifac[i] = ifac[i+1]*(i+1);

  n = read(); // 2e5
  m = read(); // 2e5
  k = read(); // 2e5
  rep(i,0,k) a[i] = read();

  if(k==0) { // f_3(n,m) * m!
    printf("%d\n",(C(n+m-1,2*m-1) * fac[m]).val()); // f_3 * (无序变有序 * m!)
    return 0;
  }
  rep(i,0,k-1) { // f_1
    ll len = a[i+1]-a[i]+1; // 区间长度, 两端已经放了
    rep(seg,0,len-1) polys[i].pb(C(len+seg-1,2*seg+1)); // 中间自由的元素个数
  }
  rep(i,0,2) { // f_2 首尾
    auto len = (i==0) ? a[0] : (n-a[k-1]+1);
    polys[k-1+i]= {1};
    rep(seg,1,len) polys[k-1+i].pb(C(len+seg-1,2*seg));
  }
  iota(idxs,idxs+k+1,0);
  // random_shuffle(idxs, idxs+k+1); // 随机, 防止被炸
  vector <mint> ans = solve(0,k);
  printf("%d\n",(ans[m-k] * fac[m-k]).val()); // 无序变有序 * (m-k)!
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:12:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   12 | ll read(){ll r;scanf("%lld",&r);return r;} // read
      |                ~~~~~^~~~~~~~~~~

Judge Result