- [AGC062E] Overlap Binary Tree
这题真有人抄吗?
- 2025-1-4 13:26:32 @
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int mod=998244353;
int add(int x,int y){
x+=y;
return (x<mod ? x : x-mod);
}
int qpow(int n,int m){
int s=n,ans=1;
while (m){
if (m&1)ans=(ll)ans*s%mod;
s=(ll)s*s%mod,m>>=1;
}
return ans;
}
namespace Poly{
const int N=19;
int n,tn,inv[1<<N],w[N][1<<N],iw[N][1<<N];
void init(int g){
inv[0]=inv[1]=1;
for(int i=2;i<(1<<N);i++)inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
for(int i=0;i<N;i++){
w[i][0]=iw[i][0]=1;
w[i][1]=qpow(g,(mod-1>>i+1));
iw[i][1]=qpow(w[i][1],mod-2);
for(int j=2;j<(1<<i);j++){
w[i][j]=(ll)w[i][1]*w[i][j-1]%mod;
iw[i][j]=(ll)iw[i][1]*iw[i][j-1]%mod;
}
}
}
void get_n(int m){
n=1,tn=0;
while (n<m)n<<=1,tn++;
}
void dft(int *a){
for(int i=n,t=0;i>1;i>>=1,t++){
int *W=w[tn-t-1];
for(int j=0;j<n;j+=i)
for(int k=0;k<(i>>1);k++){
int x=a[j+k],y=a[j+k+(i>>1)];
a[j+k]=add(x,y);
a[j+k+(i>>1)]=(ll)(x-y+mod)*W[k]%mod;
}
}
}
void idft(int *a){
for(int i=2,t=0;i<=n;i<<=1,t++){
int *W=iw[t];
for(int j=0;j<n;j+=i)
for(int k=0;k<(i>>1);k++){
int x=a[j+k],y=(ll)W[k]*a[j+k+(i>>1)]%mod;
a[j+k]=add(x,y),a[j+k+(i>>1)]=add(x,mod-y);
}
}
int inv=qpow(n,mod-2);
for(int i=0;i<n;i++)a[i]=(ll)inv*a[i]%mod;
}
vi mul(vi a,vi b,int ma,int mb,int m){
if (ma<0)ma=a.size();
if (mb<0)mb=b.size();
if (m<0)m=ma+mb-1;
ma=min(ma,m),mb=min(mb,m);
get_n(ma+mb-1);
a.resize(n),b.resize(n);
for(int i=ma;i<n;i++)a[i]=0;
for(int i=mb;i<n;i++)b[i]=0;
dft(a.data()),dft(b.data());
for(int i=0;i<n;i++)a[i]=(ll)a[i]*b[i]%mod;
idft(a.data()),a.resize(m);
return a;
}
vi get_inv(vi a,int m){
if (m==1)return vi{qpow(a[0],mod-2)};
vi s=get_inv(a,(m+1>>1)),ans;
get_n(m<<1);
a.resize(n),s.resize(n),ans.resize(n);
for(int i=m;i<n;i++)a[i]=0;
dft(a.data()),dft(s.data());
for(int i=0;i<n;i++)ans[i]=(ll)s[i]*(mod+2-(ll)a[i]*s[i]%mod)%mod;
idft(ans.data()),ans.resize(m);
return ans;
}
vi get_ln(vi a,int m){
if (m==1)return vi{0};
vi ans(m-1);
for(int i=1;i<m;i++)ans[i-1]=(ll)i*a[i]%mod;
ans=mul(ans,get_inv(a,m),m-1,m,m);
for(int i=m-1;i;i--)ans[i]=(ll)inv[i]*ans[i-1]%mod;
ans[0]=0;
return ans;
}
vi get_exp(vi a,int m){
if (m==1)return vi{1};
vi s=get_exp(a,(m+1>>1)),ans;
s.resize(m),ans=get_ln(s,m);
ans[0]=add(1,mod-ans[0]);
for(int i=1;i<m;i++)ans[i]=add(a[i],mod-ans[i]);
return mul(s,ans,(m+1>>1),m,m);
}
vi get_pow(vi a,int m,int k){
if (!k){
for(int i=0;i<m;i++)a[i]=(!i);
return a;
}
int t=0;
while ((t<m)&&(!a[t]))t++;
if ((ll)t*k>=m)return vi(m,0);
int s1=qpow(a[t],mod-2),s2=qpow(a[t],k);
for(int i=t;i<m;i++)a[i-t]=(ll)s1*a[i]%mod;
a=get_ln(a,m-t);
for(int i=0;i<m-t;i++)a[i]=(ll)k*a[i]%mod;
a=get_exp(a,m-t),a.resize(m);
t*=k;
for(int i=m-1;i>=t;i--)a[i]=(ll)s2*a[i-t]%mod;
for(int i=0;i<t;i++)a[i]=0;
return a;
}
};
int n,m,k,ans;
int main(){
Poly::init(3);
scanf("%d%d",&n,&k);
m=(n+1>>1);
if (k>m){puts("0");return 0;}
if ((n==1)&&(k==1)){puts("1");return 0;}
int s=1;vi v0(n,0),v1(n,0);
for(int i=1;i<m;i++){
s=(ll)s*i%mod;
v0[i]=s,v1[i]=(ll)s*i%mod;
}
vi v=Poly::mul(Poly::get_pow(v0,n,k),Poly::get_pow(v1,n,m-k),n,n,n);
ans=2LL*s*v[n-1]%mod,s=1;
for(int i=1;i<=k;i++)s=(ll)s*i%mod;
for(int i=1;i<=m-k;i++)s=(ll)s*i%mod;
ans=(ll)ans*qpow(s,mod-2)%mod;
printf("%d\n",ans);
return 0;
}
2 条评论
-
friend_me LV 6 @ 2025-1-5 11:40:13
这啥?
-
2025-1-4 16:07:51@
这是什么?
- 1
信息
- ID
- 19611
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 4
- 已通过
- 2
- 上传者