Submission #49633712

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/modint>
#include <atcoder/convolution>
const int MOD=998244353;
using mint = atcoder::static_modint<MOD>;
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);)
ll read(){ll r;scanf("%lld",&r);return r;}
const int N=524288; // 1<<19
mint fac[N+10]={1};
mint ifac[N+10];

vector<mint> g(N+10,0); // 1/i, g(0)=0
vector<mint> f(N+10,0); // ans
vector<mint> h(N+10,0); // h[i]=f[i]/(i!i!)

// $f(s)=s!(s-1)! (g\star h)[s]$
void calc(int l,int r) { // [l,r)
  assert(r-1 <= N);
  if(l+1==r){
    if(l == 0) {
      f[0] = 1;
      h[0] = 1;
    }else{
      f[l] *= fac[l]*fac[l-1]; // 未到点之前都是 g * h
      h[l] = f[l]*ifac[l]*ifac[l];
    }
    return ;
  }
  int mid = (l+r)/2;
  calc(l,mid);
  // [l,mid) -> [mid,r)
  vector<mint> _h;
  rep(i,l,mid) _h.push_back(h[i]); // [l,mid)
  vector<mint> _g;
  rep(i,0,r-l) _g.push_back(g[i]); // [0,r-l)
  auto res = atcoder::convolution(_h,_g);
  rep(i,mid,r) f[i] += res[i-l];
  calc(mid,r);
}

int main(){
  rep(i,1,N+1) fac[i]=fac[i-1]*i;
  ifac[N] = fac[N].pow(MOD-2);
  per(i,0,N) ifac[i]=ifac[i+1]*(i+1);
  rep(i,1,N+1) g[i]=ifac[i]*fac[i-1];
  int n=read();
  mint ans = fac[n]*fac[n] + fac[n]; // all(n!n!) - alice - bob + alice&bob(n!)
  int bound = 1;
  while(bound <= n) bound*=2;
  calc(0, bound);
  ans -= 2*f[n];
  printf("%d\n",ans.val());
  return 0;
}

Submission Info

Compile Error

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

Judge Result