【CF1580F】Problems for Codeforces
Description
给出\(n,m\)
求满足条件的序列\(a\)个数：
\(a_i+a_{i+1}<m,a_1+a_n<m\)
模\(998244353\)
Input
一行两个数\(n,m\)
Output
一行一个数表示答案
Sample Input
3 2
Sample Output
4
Data Constraint
\(1\le n\le 5*10^4,1\le m\le 10^9\)
Solution
参考EI给出的\(O(n\log n)\)做法
1.\(n~is~even\)
把条件变为\(a_1<m-a_1>a_2<\cdots>a_{n-1}<m-a_n>a_1\)
于是可以对\(b\)计数：\(b_1\le b_2\ge b_3\le\cdots\ge b_{n-1}\le b_n\ge b_1\)
其中\(b_i\in[0,m)\)
于是可以对不等号容斥，然后一段一段拼接
\[F=\sum_{l=1}\binom{m+l}{2l}x^{2l}\\ G=\sum_{l=1}l\binom{m+l}{2l}x^{2l}\\ Ans=[x^n](-1)^{\frac{n}{2}-1}\frac{G}{1+F} \]2.\(n~is~odd\)
考虑将\(\ge\lceil\frac{m}{2}\rceil\)视为大数，其它视为小数，于是原序列变成许多大小交替的段的拼接
将大数减去\(\lceil\frac{m}{2}\rceil\)，于是得到了一个\(\lfloor\frac{m}{2}\rfloor\)的子问题
这个时候可以套用\(n\)为偶数的做法
要注意的是，当\(m\)为奇数时，长度为\(1\)的段要额外加一
将断环后的序列看成是偶数段最后面接奇数段
于是得到了
\[F=\sum_{l=1}\binom{\lfloor\frac{m}{2}\rfloor+l}{2l}x^{2l}(-1)^l\\ G=\sum_{l=1}\binom{\lfloor\frac{m}{2}\rfloor+l-1}{2l-1}x^{2l-1}(-1)^l\\ H=\frac{G}{1+F}+[m~is~odd]\\ Ans=[x^n]\frac{1}{1-H^2}\sum_{l=1}(2l-1)H_{2l-1}x^{2l-1}\\ \]Code
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define N 600010
#define mo 998244353
#define LL long long
#define ULL unsigned long long
int rev[N],G1[N],G2[N],fac[N],ifac[N],inv[N];
int mod(int x){return x>=mo?x-mo:x;}
int mi(int x,int y){
if(!y)return 1;
if(y==1)return x;
return y%2?1ll*x*mi(1ll*x*x%mo,y/2)%mo:mi(1ll*x*x%mo,y/2);
}
void init(){
fac[0]=ifac[0]=1;
F(i,1,N-10)fac[i]=1ll*fac[i-1]*i%mo,inv[i]=(i==1?1:1ll*mo/i*mod(mo-1ll*inv[mo%i]%mo)%mo);
ifac[N-10]=mi(fac[N-10],mo-2);
Fd(i,N-11,1)ifac[i]=1ll*ifac[i+1]*(i+1)%mo;
for(int l=1;l<=N-10;l<<=1)G1[l]=mi(3,(mo-1)/(l*2)),G2[l]=mi(G1[l],mo-2);
}
void BRT(int x){F(i,0,x-1)rev[i]=(rev[i>>1]>>1)|((i&1)?(x>>1):0);}
struct poly{
vector<int>val;
poly(int x=0){if(x)val.push_back(x);}
poly(const vector<int>&x){val=x;}
void Rev(){reverse(val.begin(),val.end());}
void ins(int x){val.push_back(x);}
void clear(){vector<int>().swap(val);}
int sz(){return val.size();}
void rsz(int x){val.resize(x);}
void shrink(){for(;sz()&&!val.back();val.pop_back());}
poly modxn(int x){
if(val.size()<=x)return poly(val);
else return poly(vector<int>(val.begin(),val.begin()+x));
}
int operator[](int x)const{
if(x<0||x>=val.size())return 0;
return val[x];
}
void NTT(int x){
static ULL f[N],w[N];
w[0]=1;
F(i,0,sz()-1)f[i]=(((LL)mo<<5)+val[rev[i]])%mo;
for(int mid=1;mid<sz();mid<<=1){
int tmp=(x==1?G1[mid]:G2[mid]);
F(i,1,mid-1)w[i]=w[i-1]*tmp%mo;
for(int i=0;i<sz();i+=(mid<<1)){
F(j,0,mid-1){
int t=w[j]*f[i|j|mid]%mo;
f[i|j|mid]=f[i|j]+mo-t;f[i|j]+=t;
}
}
if(mid==(1<<10)){F(i,0,sz()-1)f[i]%=mo;};
}
if(x==-1){int tmp=inv[sz()];F(i,0,sz()-1)val[i]=f[i]%mo*tmp%mo;}
else{F(i,0,sz()-1)val[i]=f[i]%mo;}
}
void DFT(){NTT(1);}
void IDFT(){NTT(-1);}
friend poly operator*(poly x,poly y){
if(x.sz()<30||y.sz()<30){
if(x.sz()>y.sz())swap(x,y);
poly ret;
ret.rsz(x.sz()+y.sz());
F(i,0,ret.sz()-1){
for(int j=0;j<=i&&j<x.sz();j++)
ret.val[i]=mod(ret.val[i]+1ll*x[j]*y[i-j]%mo);
}
// ret.shrink();
return ret;
}
int l=1;
while(l<x.sz()+y.sz()-1)l<<=1;
x.rsz(l);y.rsz(l);BRT(l);
x.DFT();y.DFT();
F(i,0,l-1)x.val[i]=1ll*x[i]*y[i]%mo;
x.IDFT();
// x.shrink();
return x;
}
friend poly operator+(poly x,poly y){
poly ret;
ret.rsz(max(x.sz(),y.sz()));
F(i,0,ret.sz()-1)ret.val[i]=mod(x[i]+y[i]);
return ret;
}
friend poly operator-(poly x,poly y){
poly ret;
ret.rsz(max(x.sz(),y.sz()));
F(i,0,ret.sz()-1)ret.val[i]=mod(x[i]-y[i]+mo);
return ret;
}
poly &operator*=(poly x){return (*this)=(*this)*x;}
poly &operator+=(poly x){return (*this)=(*this)+x;}
poly &operator-=(poly x){return (*this)=(*this)-x;}
poly deriv(){
poly f;
f.rsz(sz()-1);
F(i,0,sz()-2)f.val[i]=1ll*(i+1)*val[i+1]%mo;
return f;
}
poly integ(){
poly f;
f.rsz(sz()+1);
F(i,1,sz())f.val[i]=1ll*val[i-1]*inv[i]%mo;
return f;
}
poly inver(int Len){
poly f,g,res(mi(val[0],mo-2));
for(int i=1;i<Len;){
i<<=1;f.rsz(i);g.rsz(i);BRT(i);
F(j,0,i-1)f.val[j]=(*this)[j],g.val[j]=res[j];
f.DFT();g.DFT();
F(j,0,i-1)f.val[j]=1ll*f[j]*g[j]%mo;
f.IDFT();
F(j,0,(i>>1)-1)f.val[j]=0;
f.DFT();
F(j,0,i-1)f.val[j]=1ll*f[j]*g[j]%mo;
f.IDFT();
res.rsz(i);
F(j,i>>1,i-1)res.val[j]=mod(mo-f[j]);
}
return res.modxn(Len);
}
poly Sqrt(int Len){
poly f,g,res(1);
for(int i=1;i<Len;){
i<<=1;
f=res;
f.rsz(i>>1);BRT(i>>1);
f.DFT();
F(j,0,(i>>1)-1)f.val[j]=1ll*f[j]*f[j]%mo;
f.IDFT();
F(j,0,i-1)f.val[j%(i>>1)]=mod(f[j%(i>>1)]+mo-(*this)[j]);
g=(2*res).inver(i>>1);f=(f*g).modxn(i>>1);f.rsz(i);
F(j,i>>1,i-1)f.val[j]=f[j-(i>>1)];
F(j,0,(i>>1)-1)f.val[j]=0;
res-=f;
}
return res.modxn(Len);
}
poly Ln(int Len){
return (deriv()*inver(Len)).integ().modxn(Len);
}
poly Exp(int Len){
poly f(1);
for(int i=2;i<Len*2;i<<=1)f=(f*(1-f.Ln(i)+modxn(i))).modxn(i);
return f.modxn(Len);
}
poly Pow(int Len,int k){
poly f;
f.clear();
int tail=0;
while(val[tail]==0&&tail<sz())tail++;
if(tail>=sz())return f;
if(tail*k>=Len)return f;
f.rsz(Len);
int Mul=mi(val[tail],mo-2);
F(i,0,min(Len-1,sz()-tail-1))f.val[i]=1ll*val[i+tail]*Mul%mo;
Mul=mi(val[tail],k);
f=f.Ln(Len);
F(i,0,Len-1)f.val[i]=1ll*f[i]*(k%mo)%mo;
f=f.Exp(Len);
Fd(i,Len-1,tail*k)f.val[i]=1ll*f[i-tail*k]*Mul%mo;
F(i,0,tail*k-1)f.val[i]=0;
return f;
}
};
int n,m,C[N];
int main(){
init();
scanf("%d%d",&n,&m);
if(n&1){
int w=m/2;
poly f,g;
f.rsz(n+1);g.rsz(n+1);
C[0]=1;
F(i,0,n-1)C[i+1]=1ll*C[i]*inv[2*i+1]%mo*inv[2*i+2]%mo*(w-i)%mo*(w+i+1)%mo;
F(l,1,n/2)f.val[2*l]=1ll*C[l]*(l&1?mo-1:1)%mo;
C[1]=w;
F(i,1,n-1)C[i+1]=1ll*C[i]*inv[2*i+1]%mo*inv[2*i]%mo*(w-i)%mo*(w+i)%mo;
F(l,1,n/2+1)g.val[2*l-1]=1ll*C[l]*(l&1?1:mo-1)%mo;
poly h=((1+f).inver(n+1)*g).modxn(n+1);
if(m&1)h.val[1]=mod(h[1]+1);
poly p;
p.rsz(n+1);
F(l,1,n/2+1)p.val[2*l-1]=1ll*(2*l-1)*h[2*l-1]%mo;
h=(h*h).modxn(n+1);
h=(1-h).inver(n+1);
p=(p*h).modxn(n+1);
printf("%d",p[n]);
}else{
C[0]=1;
F(i,0,n-1)C[i+1]=1ll*C[i]*inv[2*i+1]%mo*inv[2*i+2]%mo*(m-i)%mo*(m+i+1)%mo;
poly f,g;
f.rsz(n+1);g.rsz(n+1);
F(l,1,n/2)f.val[2*l]=C[l],g.val[2*l]=1ll*C[l]*l%mo;
poly h=((1+f).inver(n+1)*g).modxn(n+1);
printf("%d",1ll*h[n]*((n/2-1)&1?mo-1:1)%mo);
}
return 0;
}