记录编号	488624	评测结果	AATTTTTTTT
题目名称	[HZOI 2015] 有标号的DAG计数 II	最终得分	20
用户昵称	支羽	是否通过	未通过
代码语言	C++	运行时间	8.695 s
提交时间	2018-02-22 19:52:59	内存使用	7.43 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#define LL long long
#define FILE "dag_count"
//#define FILE "分治"
#define Mod (998244353)
#define G (3)
#define sq2 (116195171)
#define rg register
using namespace std;

const int N = 300010;
int fac[N],facInv[N],Pow[N],Inv[N];
int rev[N],a[N],b[N],f[N],gn[N];

inline int gi(){
  int x=0,res=1;char ch=getchar();
  while(ch>'9' || ch<'0')res^=ch=='-',ch=getchar();
  while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
  return res?x:-x;
}

inline int QPow(int d,int z,int ans=1){
  for(;z;z>>=1,d=1ll*d*d%Mod)
    if(z&1)ans=1ll*ans*d%Mod;
  return ans;
}

inline void prepare(int n){
  for(int i=1;i<=n+n+2;i<<=1)
    gn[i]=QPow(G,(Mod-1)/(i<<1));
  fac[0]=Pow[0]=1;
  for(int i=1;i<=n;++i)
    fac[i]=1ll*fac[i-1]*i%Mod;
  facInv[n]=QPow(fac[n],Mod-2);
  for(int i=n-1;i>=0;--i)
    facInv[i]=1ll*facInv[i+1]*(i+1)%Mod;
  for(int i=0;i<=n;++i){
    Pow[i]=QPow(sq2,1ll*i*i%(Mod-1));
    Inv[i]=QPow(Pow[i],Mod-2);
  }
}

inline void NTT(int *A,int n,int f){
  for(int i=1;i<n;++i)
    if(i<rev[i])swap(A[i],A[rev[i]]);
  for(int i=1;i<n;i<<=1){
    for(int j=0;j<n;j+=(i<<1)){
      rg int g=1,x,y;
      for(int k=0;k<i;++k,g=1ll*g*gn[i]%Mod){
        x=A[j+k];y=1ll*g*A[i+j+k]%Mod;
        A[j+k]=(x+y)%Mod;A[i+j+k]=(x-y)%Mod;
      }
    }
  }
  if(f==1)return;reverse(A+1,A+n);
  int iv=QPow(n,Mod-2);
  for(int i=0;i<n;++i)A[i]=1ll*A[i]*iv%Mod;
}

inline void solve(int l,int r){
  if(l==r){f[l]=(f[l]%Mod+Mod)%Mod;return;}
  int mid=(l+r)>>1,n=1,L=0;
  solve(l,mid);
  for(;n<=r+mid-l-l;n<<=1)L++;
  for(int i=0;i<n;++i)
    rev[i]=(rev[i/2]/2)|((i&1)<<(L-1));
  for(int i=l;i<=mid;++i)a[i-l]=f[i];
  for(int i=1,j=1;i<=r-l;++i,j=-j)
    b[i]=1ll*j*facInv[i]*Inv[i]%Mod;
  NTT(a,n,1);NTT(b,n,1);
  for(int i=0;i<n;++i)a[i]=1ll*a[i]*b[i]%Mod;
  NTT(a,n,-1);
  for(int i=mid+1;i<=r;++i)f[i]=(f[i]+a[i-l])%Mod;
  for(int i=0;i<n;++i)a[i]=b[i]=0;
  solve(mid+1,r);
}

int main(){
  freopen(FILE".in","r",stdin);
  freopen(FILE".out","w",stdout);
  int n=gi();prepare(n);f[0]=1;
  solve(0,n);f[n]=(f[n]+Mod)%Mod;
  f[n]=1ll*f[n]*fac[n]%Mod*Pow[n]%Mod;
  printf("%d\n",f[n]);  
  fclose(stdin);fclose(stdout);
  return 0;
}