当前位置：首页 > news >正文

做shopify网站/网站的收录情况怎么查

news 2025/7/1 2:32:57

做shopify网站,网站的收录情况怎么查,旅游网站内容规划,免费创建社区论坛网站官方题解：http://codeforces.com/blog/entry/54233 就是由简入繁 1.序列处理，只考虑一个半圆 2.环形处理（其实这个就是多了旋转同构） 然后基于分割线邻居的跨越与否，分类讨论 g->没有分割线方案数（其实也…

官方题解：
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('\n');
}
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+lenfor(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 lengthfor(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 1memcpy(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;
/f0memset(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
*/