官方题解：
http://codeforces.com/blog/entry/54233
就是由简入繁
1.序列处理，只考虑一个半圆
2.环形处理（其实这个就是多了旋转同构）
然后基于分割线邻居的跨越与否，分类讨论
g->没有分割线方案数（其实也可以变成贡献，但是太简单，之后乘上(i+0/1/2）也方便）
f0->有分割线，两边都没有选所有情况的贡献的和
f1->有分割线，两边选择了一个所有情况的贡献的和
f2->有分割线，两边都选择了所有情况的贡献的和
最后对于环
考虑除了中间割线，顺时针第一个割线的位置i，再对于跨越与否分4种情况讨论。可以逆时针旋转(i-2)个
对于式子，可以分治FFT
或者大力解二元方程，变成多项式求逆
代码：
#include<bits/stdc++.h> #define reg register int #define il inline #define int long long #define numb (ch^'0') using namespace std; typedef long long ll; template<class T>il void rd(T &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } template<class T>il void ot(T x){ x/10?ot(x/10):putchar(x%10+'0'); } template<class T>il void prt(T a[],int st,int nd){ for(reg i=st;i<=nd;++i) printf("%lld ",a[i]);putchar(' '); } namespace Miracle{ const int N=8*50000+5; const int mod=998244353; const int G=3; const int GI=332748118; int n; ll f0[N],f1[N],f2[N]; ll g[N],g0[N],g1[N],g2[N]; ll x3g2[N],g12[N],ix3g2[N]; ll ni[N],t[N],p[N],l[N],q[N]; ll qm(ll x,ll y){ ll ret=1; while(y){ if(y&1) ret=(ll)ret*x%mod; x=(ll)x*x%mod; y>>=1; } return ret; } int rev[N]; void NTT(ll *f,int n,int typ){ // cout<<n<<endl; for(reg i=0;i<n;++i){ if(i<rev[i]) swap(f[i],f[rev[i]]); } for(reg p=2;p<=n;p<<=1){ ll gen; if(typ==1) gen=qm(G,(mod-1)/p); else gen=qm(GI,(mod-1)/p); for(reg l=0;l<n;l+=p){ ll buf=1; for(reg k=l;k<l+p/2;++k){ ll tmp=f[k+p/2]*buf%mod; f[k+p/2]=(f[k]-tmp+mod)%mod; f[k]=(f[k]+tmp)%mod; buf=buf*gen%mod; } } } } void calc(ll *f,ll *g,int n){ for(reg i=0;i<n;++i){ rev[i]=(rev[i>>1]>>1)|((i&1)?n>>1:0); } NTT(f,n,1);NTT(g,n,1); for(reg i=0;i<n;++i) f[i]=f[i]*g[i]%mod; NTT(f,n,-1); ll iv=qm(n,mod-2); for(reg i=0;i<n;++i) f[i]=f[i]*iv%mod; } void add(ll *f,ll *g,int n){//n is max(len f,len g) for(reg i=0;i<n;++i){ f[i]=(f[i]+g[i])%mod; } } void sub(ll *f,ll *g,int n){ for(reg i=0;i<n;++i){ f[i]=(f[i]-g[i]+mod)%mod; } } void inv(ll *f,ll *g,int n){ // cout<<" inv "<<n<<endl; if(n==1){ g[0]=qm(f[0],mod-2);return; } inv(f,g,n>>1); for(reg i=0;i<n;++i) t[i]=f[i]; for(reg i=n;i<2*n;++i) t[i]=0; for(reg i=0;i<2*n;++i){ rev[i]=(rev[i>>1]>>1)|((i&1)?n:0); } NTT(t,2*n,1);NTT(g,2*n,1); for(reg i=0;i<2*n;++i){ g[i]=(2+mod-t[i]*g[i]%mod)%mod*g[i]%mod; } NTT(g,2*n,-1); ll iv=qm(2*n,mod-2); for(reg i=0;i<n;++i) g[i]=g[i]*iv%mod; for(reg i=n;i<2*n;++i) g[i]=0; } void tran(ll *f,int len,int n){//warning!! bac to length=length+len for(reg i=n-1+len;i>=len;--i){ f[i]=f[i-len]; } for(reg i=0;i<len;++i) f[i]=0; } int main(){ rd(n); g[0]=1;g[1]=0;g[2]=1;g[3]=0; int lp; for(lp=1;lp<=n+n+4;lp<<=1);//warning!! biggest length for(reg i=4;i<=n;++i){ g[i]=(g[i-2]+g[i-4])%mod; } for(reg i=0;i<=n;++i){ g0[i]=g[i]*i%mod*i%mod; g1[i]=g[i]*(i+1)%mod*(i+1)%mod; g2[i]=g[i]*(i+2)%mod*(i+2)%mod; } l[0]=1; // cout<<lp<<endl; // x3g2[0]=1; // memcpy(p,g2,sizeof g2);tran(p,3,n+1); // sub(x3g2,p,lp); // inv(x3g2,ix3g2,lp); // cout<<" ix3g2 "<<endl; // prt(ix3g2,0,lp-1); memcpy(p,g2,sizeof g2); tran(p,3,n+1); sub(l,p,lp); memcpy(p,g0,sizeof g0); tran(p,1,n+1); sub(l,p,lp); memcpy(p,g0,sizeof g0); memcpy(q,g2,sizeof g2); calc(p,q,lp); tran(p,4,lp); add(l,p,lp); memcpy(p,g1,sizeof g1); memcpy(q,g1,sizeof g1); calc(p,q,lp); tran(p,4,lp); sub(l,p,lp); inv(l,ni,lp); for(reg i=n+1;i<lp;++i) ni[i]=0; //////////////////////inv 1 memcpy(l,g0,sizeof g0); memcpy(p,g0,sizeof g0); memcpy(q,g2,sizeof g2); calc(p,q,lp); tran(p,3,lp); sub(l,p,lp); memcpy(p,g1,sizeof g1); memcpy(q,g1,sizeof g1); calc(p,q,lp); tran(p,3,lp); add(l,p,lp); for(reg i=n+1;i<lp;++i) l[i]=0; calc(l,ni,lp); memcpy(f0,l,sizeof l); for(reg i=n+1;i<lp;++i) f0[i]=0; /////////////////////f0 memset(l,0,sizeof l); l[0]=1; memcpy(p,g2,sizeof g2); tran(p,3,n+1); sub(l,p,lp); memset(ni,0,sizeof ni); inv(l,ni,lp); for(reg i=n+1;i<lp;++i) ni[i]=0; // prt(ni,0,lp-1); memcpy(l,g1,sizeof g1); memcpy(p,g1,sizeof g1); tran(p,1,n+1); // cout<<" ll "<<endl; // prt(p,0,lp-1); memcpy(q,f0,sizeof f0); //prt(q,0,lp-1); calc(p,q,lp); add(l,p,lp); for(reg i=n+1;i<lp;++i) l[i]=0; memcpy(p,ni,sizeof ni); calc(l,p,lp); memcpy(f1,l,sizeof l); for(reg i=n+1;i<lp;++i) f1[i]=0; ///////////////////////f1 memcpy(l,g2,sizeof g2); memcpy(p,g1,sizeof g1); tran(p,1,n+1); memcpy(q,f1,sizeof f1); calc(p,q,lp); add(l,p,lp); for(reg i=n+1;i<lp;++i) l[i]=0; // memcpy(p,ni,sizeof ni); calc(l,ni,lp); memcpy(f2,l,sizeof l); /////////////////////f2 // cout<<"f0 "<<endl; // for(reg i=0;i<n;++i){ // cout<<f0[i]<<" "; // }cout<<endl; // cout<<"f1 "<<endl; // for(reg i=0;i<n;++i){ // cout<<f1[i]<<" "; // }cout<<endl; // cout<<"f2 "<<endl; // for(reg i=0;i<n;++i){ // cout<<f2[i]<<" "; // }cout<<endl; ll ans=(ll)n*(g[n-1]+g[n-3])%mod*(n-1)%mod*(n-1)%mod; for(reg i=2;i<=n;++i){ ll tmp=0; tmp=(tmp+g[i-2]*f0[n-i]%mod*(i-2)%mod*(i-2)%mod)%mod; if(i>2&&i<n) tmp=(tmp+g[i-3]*f1[n-i-1]%mod*2%mod*(i-2)%mod*(i-2)%mod)%mod; if(i>3&&i<n-1) tmp=(tmp+g[i-4]*f2[n-i-2]%mod*(i-2)%mod*(i-2)%mod)%mod; tmp=tmp*(i-1)%mod; ans=(ans+tmp)%mod; } cout<<ans; return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/2/27 15:57:21 */
总结：
0.拆开，只考虑一个半圆
1.由于贡献是根据割线统计的，推DP式子时候根据割线的跨越与否进行统计