QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#381587#6196. Minimum Element ProblemJohnAlfnovRE 0ms0kbC++145.4kb2024-04-07 19:07:292024-04-07 19:07:30

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 19:07:30]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2024-04-07 19:07:29]
  • 提交

answer

//Code by Lightningfall
//Start coding on ????/??/??
//Finish debugging on ????/??/??
#include<bits/stdc++.h>
#define mod 998244353
#define poly vector<int>
#define N 21
using namespace std;
void output(poly a){
	for(auto cu:a)printf("%d ",cu);
	printf("\n");
}
poly mul(int k,poly a){
	int sz=a.size();
	poly b;
	for(int i=0;i<sz;++i)b.emplace_back(1ll*k*a[i]%mod);
	return b;
}
poly plu(poly a,poly b){
	poly c;
	int s1=a.size(),s2=b.size();
	c.resize(max(s1,s2));
	for(int i=0;i<s1;++i)c[i]=(c[i]+a[i])%mod;
	for(int i=0;i<s2;++i)c[i]=(c[i]+b[i])%mod;
	return c;
}
int powdv(int x,int y=mod-2){
	int ans=1;
	while(y){
		if(y&1)ans=1ll*ans*x%mod;
		y>>=1,x=1ll*x*x%mod;
	}
	return ans;
}
int a[1<<N],b[1<<N],ap[1<<N],bp[1<<N];
int rev[1<<N];
void getrev(int l){
	rev[0]=0;
	for(int i=1;i<=l;++i){
		for(int j=0;j<(1<<(i-1));++j){
			rev[j^(1<<(i-1))]=rev[j]^(1<<(l-i));
		}
	}
}
void ntt(int l,int *c,int *d,int cd){
	for(int i=0;i<(1<<l);++i)d[i]=c[rev[i]];
	for(int i=1;i<(1<<l);i<<=1){
		int o1=powdv(3,(mod-1)/i/2);
		if(cd==-1)o1=powdv(o1);
		for(int j=0;j<(1<<l);j+=i+i){
			int o=1;
			for(int k=j;k<j+i;++k){
				int A=d[k],B=d[k+i];
				d[k]=(A+1ll*o*B)%mod,d[k+i]=(A-1ll*o*B)%mod;
				o=1ll*o*o1%mod;
			}
		}
	}
	if(cd==-1){
		int ny=powdv(1<<l);
		for(int i=0;i<(1<<l);++i)d[i]=1ll*d[i]*ny%mod;
	}
}
poly multi(vector<poly>g){
	int sz=0;
	for(auto p:g)sz+=p.size()-1;
	int ss=sz+1;
	while(ss&(ss-1))++ss;
	int l=__builtin_ctz(ss);
	getrev(l);
	for(int i=0;i<(1<<l);++i)ap[i]=1;
	for(auto p:g){
		int zz=p.size();
		for(int i=0;i<(1<<l);++i){
			a[i]=(i<zz?p[i]:0);
		}
		ntt(l,a,bp,1);
		for(int i=0;i<(1<<l);++i)ap[i]=1ll*ap[i]*bp[i]%mod;
	}
	ntt(l,ap,b,-1);
	poly ans;
	for(int i=0;i<=sz;++i)ans.emplace_back((b[i]+mod)%mod);
	return ans;
}
poly deri(poly a){
	if((signed)a.size()==1)return {0};
	int sz=a.size();
	poly b;
	for(int i=1;i<sz;++i)b.emplace_back(1ll*i*a[i]%mod);
	return b;
}
int id[1<<N],di[1<<N],ny[1<<N];
int C(int n,int m){
	if(n<0||m<0||n<m)return 0;
	return 1ll*di[n]*id[m]%mod*id[n-m]%mod;
}
void init(int sz){
	di[0]=1;
	for(int i=1;i<=sz;++i)di[i]=1ll*i*di[i-1]%mod;
	id[sz]=powdv(di[sz]);
	for(int i=sz-1;i>=0;--i)id[i]=1ll*id[i+1]*(i+1)%mod;
	for(int i=1;i<=sz;++i)ny[i]=1ll*id[i]*di[i-1]%mod;
}
poly inte(poly a){
	int sz=a.size();
	init(sz);
	poly b;
	b.emplace_back(0);
	for(int i=0;i<sz;++i)b.emplace_back(1ll*ny[i+1]*a[i]%mod);
	return b;
}
poly mo(poly a,int n){
	poly b;
	int sz=min((signed)a.size(),n);
	for(int i=0;i<sz;++i)b.emplace_back(a[i]);
	return b;
}
poly inver(poly a,poly b,int n,int cs){
	if(cs==0)return b;
	int zz=min(2*(signed)b.size(),n);
	b=mo(plu(mul(2,b),mul(mod-1,multi({b,b,mo(a,2*b.size())}))),zz);
	return inver(a,b,n,cs-1);
}
poly inv(poly a,int n){
	poly b={1};
	int cc=1,gs=1;
	while(cc<=n)cc*=2,++gs;
	return inver(a,b,n,gs);
}
poly ln(poly a){
	poly pp=mo(multi({deri(a),inv(a,a.size())}),a.size()-1);
	return inte(pp);
}
const int B=16;
int aa[500005],bb[500005];
void solve(int l,int r){
	if(r-l<=50){
		for(int i=l;i<r;++i){
			int he=0;
			for(int j=l;j<i;++j){
				he=(he+1ll*bb[j]*aa[i-j])%mod;
			}
			bb[i]=1ll*(bb[i]+he)*ny[i]%mod;
		}
		return;
	}
	int fd[B+5];
	for(int i=0;i<B;++i)fd[i]=l+(r-l)/B*i;
	fd[B]=r;
	int mx=0;
	for(int i=0;i<B;++i)mx=max(mx,fd[i+1]-fd[i]);
	int pp=mx;
	mx=3*mx+1;
	while(mx&(mx-1))++mx;
	int L=__builtin_ctz(mx);
	getrev(L);
	vector<int>vv;
	for(int i=0;i<(1<<L);++i)vv.emplace_back(rev[i]);
	vector<int>pt[B];
	for(int i=0;i<B;++i){
		for(int j=0;j<(1<<L);++j)a[j]=0;
		for(int j=fd[i]-l;j<fd[i]-l+2*pp&&j<r;++j)a[j-fd[i]+l]=aa[j];
		ntt(L,a,ap,1);
		for(int j=0;j<(1<<L);++j)pt[i].emplace_back(ap[j]);
	}
	vector<int>tp[B];
	for(int i=0;i<B;++i){
		for(int k=0;k<(1<<L);++k)ap[k]=0;
		for(int j=0;j<i;++j){
			for(int k=0;k<(1<<L);++k)
				ap[k]=(ap[k]+1ll*tp[j][k]*pt[i-j-1][k])%mod;
		}
		ntt(L,ap,a,-1);
		for(int k=fd[i];k<fd[i+1];++k)
			bb[k]=(bb[k]+a[k-fd[i]+(fd[1]-fd[0])])%mod;
		solve(fd[i],fd[i+1]);
		for(int k=0;k<(1<<L);++k)rev[k]=vv[k];
		for(int k=0;k<(1<<L);++k){
			a[k]=(k<fd[i+1]-fd[i]?bb[fd[i]+k]:0);
		}
		ntt(L,a,ap,1);
		for(int k=0;k<(1<<L);++k)tp[i].emplace_back(ap[k]);
	}
}
poly exp(poly a){
	int n=a.size();
	init(n);
	for(int i=0;i<n;++i)aa[i]=1ll*i*a[i]%mod,bb[i]=0;
	bb[0]=1;
	for(int i=1;i<n;++i)bb[i]=(bb[i]+aa[i])%mod;
	solve(1,n);
	poly b;
	for(int i=0;i<n;++i)b.emplace_back((bb[i]+mod)%mod);
	return b;
}
int ans[500005],ka[500005];
int qiu(int z,int k){
	k-=z;--z;
	if(k<0)return 0;
	return (C(z+2*k,k)-C(z+2*k,k-1)+mod)%mod;
}
int main(){
	freopen("schrodingerstomb.in","r",stdin);
	freopen("schrodingerstomb.out","w",stdout);
	int n,x;
	scanf("%d%d",&n,&x);
	init(2*n);
	int s=x,t=n-x+1;
	poly z1(s+1),z2(t+1);
	for(int i=1;i<=s;++i){
		z1[i]=1ll*id[i-1]*qiu(i,s)%mod;
	}
	for(int i=1;i<=t;++i){
		z2[i]=1ll*id[i-1]*qiu(i,t)%mod;
	}
	poly zz=multi({z1,z2});
	for(int i=2;i<=n+1;++i){
		int xs=1ll*di[i-2]*zz[i]%mod;
		ans[i-1]=(ans[i-1]+xs)%mod;
	}
	for(int i=0;i<=n;++i){
		ka[i]=(C(2*i,i)-C(2*i,i-1)+mod)%mod;
	}
	poly p1(s+1),p2(t+1);
	for(int i=1;i<=s;++i)p1[i]=ka[i-1];
	for(int i=1;i<=t;++i)p2[i]=ka[i-1];
	poly pp=multi({p1,p2});
	for(int i=2;i<=s+t;++i){
		ans[n-i+3]=(ans[n-i+3]-1ll*ka[n-i+1]*pp[i]%mod+mod)%mod;
	}
	for(int i=2;i<=n;++i)ans[i]=(ans[i]+ans[i-1])%mod;
	for(int i=1;i<=n;++i){
		printf("%d\n",(ans[i]+mod)%mod);
	}
	return 0;
}

详细

Test #1:

score: 0
Dangerous Syscalls

input:

5 2

output:


result: