Submission #70663472

---

Source Code Expand

#include<bits/stdc++.h>
//bool Mst;
using namespace std;
namespace wyzfastio
{
	namespace __getchar{const int bufsize=1<<22;char buf[bufsize],*p1=buf,*p2=buf;inline char getchar(){return (p1==p2&&(p2=(p1=buf)+fread(buf,1,bufsize,stdin),p1==p2))?EOF:(*p1++);}}using __getchar::getchar;namespace __putchar{const int bufsize=1<<22;char buf[bufsize],*p=buf;inline void putchar(const char ch){if(p-buf==bufsize) fwrite(buf,1,bufsize,stdout),p=buf;*p++=ch;}inline void flush(){fwrite(buf,1,p-buf,stdout),p=buf;}}using __putchar::putchar;using __putchar::flush;namespace __flusher{struct Flusher{Flusher(){}~Flusher(){flush();}}flusher;}
	std::string bool_str[2]={"false","true"};int double_mx=12;struct istream{void tie([[maybe_unused]]int x){}};struct ostream{void tie([[maybe_unused]]int x){}};istream in;ostream out;
	istream &operator>>(istream &in,char &s){s=getchar();while(s==' '||s=='\n'||s=='\r')s=getchar();return in;}istream &operator>>(istream &in,std::string &s){char ch=getchar();s.clear();while(ch==' '||ch=='\n'||ch=='\r')ch=getchar();while(!(ch==' '||ch=='\n'||ch=='\r'||ch==EOF))s+=ch,ch=getchar();return in;}istream &operator>>(istream &in,__int128 &x){char ch=getchar();int o=0;__int128 r=0;while(ch<'0'||ch>'9'){if(ch=='-')o^=1;ch=getchar();}while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=o?-r:r;return in;}istream &operator>>(istream &in,unsigned __int128 &x){char ch=getchar();__int128 r=0;while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=r;return in;}
	ostream &operator<<(ostream &out,const char x){putchar(x);return out;}ostream &operator<<(ostream &out,const char *s){while(*s!='\0'&&*s!=EOF)putchar(*s),s++;return out;}ostream &operator<<(ostream &out,std::string s){for(char ch:s)putchar(ch);return out;}ostream &operator<<(ostream &out,__int128 x){static int __stk[66];int top=0,op=1-((x<0)<<1);if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10)*op,x/=10;if(op==-1)putchar('-');while(top)putchar(__stk[--top]+'0');return out;}ostream &operator<<(ostream &out,unsigned __int128 x){static int __stk[66];int top=0;if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10),x/=10;while(top)putchar(__stk[--top]+'0');return out;}
	template<typename _Tp>inline typename std::enable_if<std::is_integral<_Tp>::value&&!std::is_same<_Tp,bool>::value,istream &>::type operator>>(istream &in,_Tp &x){char ch=getchar();int o=0;_Tp r=0;while(ch<'0'||ch>'9'){if(ch=='-')o^=1;ch=getchar();}while(ch>='0'&&ch<='9')r=(r<<3)+(r<<1)+ch-'0',ch=getchar();x=o?-r:r;return in;}template<typename _Tp>inline typename std::enable_if<std::is_same<_Tp,bool>::value,istream &>::type operator>>(istream &in,_Tp &x){int r;in>>r;x=r;return in;}template<typename _Tp>inline typename std::enable_if<std::is_floating_point<_Tp>::value,istream &>::type operator>>(istream &in,_Tp &x){_Tp r=0,p=1;int op=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')op=-op;ch=getchar();}while(ch>='0'&&ch<='9'){r=r*10+ch-'0';ch=getchar();}if(ch=='.'){ch=getchar();while(ch>='0'&&ch<='9')r+=(p*=0.1)*(ch-'0'),ch=getchar();}x=r*op;return in;}
	template<typename _Tp>inline typename std::enable_if<std::is_integral<_Tp>::value&&!std::is_same<_Tp,bool>::value,ostream &>::type operator<<(ostream &out,_Tp x){static int __stk[33];int top=0,op=1-((x<0)<<1);if(x==0)__stk[top++]=0;else while(x)__stk[top++]=(x%10)*op,x/=10;if(op==-1)putchar('-');while(top)putchar(__stk[--top]+'0');return out;}template<typename _Tp>inline typename std::enable_if<std::is_same<_Tp,bool>::value,ostream &>::type operator<<(ostream &out,_Tp x){out<<bool_str[x];return out;}template<typename _Tp>inline typename std::enable_if<std::is_floating_point<_Tp>::value,ostream &>::type operator<<(ostream &out,_Tp x){if(x<0)putchar('-'),x=-x;static int __stk[233];int top=0;for(int i=0;i<double_mx;i++)x*=10;x=std::floor(x+0.5);for(_Tp y;x>=1;)y=std::floor(x/10),__stk[top++]=x-y*10,x=y;while(top<=double_mx)__stk[top++]=0;while(top>double_mx)putchar(__stk[--top]+'0');putchar('.');while(top)putchar(__stk[--top]+'0');return out;}
	namespace oshelper{struct ostreamhelper{};struct endler{};endler _endl;ostreamhelper set_bool_str(const std::string str_false,const std::string str_true){bool_str[0]=str_false,bool_str[1]=str_true;return ostreamhelper();}ostreamhelper set_precision(int precision){double_mx=precision;return ostreamhelper();}ostream &operator<<(ostream &out,[[maybe_unused]]ostreamhelper outhelper){return out;}ostream &operator<<(ostream &out,[[maybe_unused]]endler _endl){out<<"\n",flush();return out;}}
#ifdef LOCAL
#define endl wyzfastio::oshelper::_endl
#else
#define endl "\n"
#endif
#define cin wyzfastio::in
#define cout wyzfastio::out
}
using ll=long long;
using ld=long double;
//#define int ll
using pii=pair<int,int>;
const int N=1e6+5,mod=998244353;
inline ll rd(ll x,ll M=mod){return x>=M?x-M:x;}
inline ll pr(ll x,ll M=mod){return x<0?x+M:x;}
inline ll qpow(ll a,ll b,ll M=mod){ll res=1;while(b){if(b&1)res=1ll*res*a%M;b>>=1,a=1ll*a*a%M;}return res;}
namespace POLY
{
	const int B=3,iB=qpow(B,mod-2);
	int pwB[23],pwiB[23],rev[N];
	void init()
	{
		for(int i=1,j=2;j<N;i++,j<<=1) pwB[i]=qpow(B,(mod-1)/j),pwiB[i]=qpow(iB,(mod-1)/j);
	}
	void ntt(int *a,int n,int op)
	{
		for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]);
		for(int mid=1,len=2,c=1;mid<n;mid<<=1,len<<=1,c++)
			for(int i=0,w=op>0?pwB[c]:pwiB[c];i<n;i+=len)
				for(int j=0,o=1,x,y;j<mid;j++,o=1ll*o*w%mod)
					x=a[i+j],y=1ll*o*a[i+j+mid]%mod,a[i+j]=(x+y)%mod,a[i+j+mid]=(x+mod-y)%mod;
		if(op<0)
		{
			int inv=qpow(n,mod-2);
			for(int i=0;i<n;i++) a[i]=1ll*a[i]*inv%mod;
		}
	}
	int a[N],b[N],x[N],c[N],d[N],e[N],f[N],g[N],h[N];
	void getinv(int *a,int *b,int n)
	{
		if(n==1) return b[0]=qpow(a[0],mod-2),void();
		getinv(a,b,(n+1)>>1);
		int sz=1,l=0;
		while(sz<(n<<1)) sz<<=1,l++;
		for(int i=1;i<sz;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
		for(int i=0;i<n;i++) x[i]=a[i];
		for(int i=n;i<sz;i++) x[i]=0;
		ntt(x,sz,1),ntt(b,sz,1);
		for(int i=0;i<sz;i++) b[i]=1ll*(2ll-1ll*x[i]*b[i]%mod+mod)%mod*b[i]%mod;
		ntt(b,sz,-1);
		for(int i=n;i<sz;i++) b[i]=0;
		for(int i=0;i<sz;i++) x[i]=0;
	}
	void diff(int *a,int *b,int n)
	{
		for(int i=1;i<n;i++) b[i-1]=1ll*i*a[i]%mod;
		return b[n-1]=0,void();
	}
	void intg(int *a,int *b,int n)
	{
		for(int i=0;i<n-1;i++) b[i+1]=1ll*qpow(i+1,mod-2)*a[i]%mod;
		return b[0]=0,void();
	}
	void mul(int *a,int *b,int *c,int n,int m)
	{
		int sz=1,l=0;
		while(sz<(n+m)) sz<<=1,l++;
		for(int i=1;i<sz;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
		for(int i=0;i<n;i++) c[i]=a[i];
		for(int i=n;i<sz;i++) c[i]=0;
		for(int i=0;i<m;i++) x[i]=b[i];
		for(int i=m;i<sz;i++) x[i]=0;
		ntt(c,sz,1),ntt(x,sz,1);
		for(int i=0;i<sz;i++) c[i]=1ll*c[i]*x[i]%mod;
		ntt(c,sz,-1);
		for(int i=n+m;i<sz;i++) c[i]=0;
		for(int i=0;i<sz;i++) x[i]=0;
	}
	void ln(int *a,int *b,int n)
	{
		diff(a,c,n),getinv(a,d,n),mul(c,d,e,n,n),intg(e,b,n);
		int sz=1;
		while(sz<(n<<1)) sz<<=1;
		for(int i=0;i<sz;i++) c[i]=d[i]=e[i]=0;
	}
	void exp(int *a,int *b,int n)
	{
		if(n==1) return b[0]=1,void();
		exp(a,b,(n+1)>>1);
		ln(b,f,n);
		int l=0,sz=1;
		while(sz<(n<<1)) sz<<=1,l++;
		for(int i=0;i<sz;i++) f[i]=(a[i]+mod-f[i])%mod;
		f[0]=(f[0]+1)%mod;
		mul(b,f,g,n,n);
		for(int i=0;i<sz;i++) b[i]=g[i],g[i]=0;
		for(int i=n;i<sz;i++) g[i]=0;
		for(int i=0;i<sz;i++) f[i]=0;
	}
	void __basic_pow(int *a,int *b,int n,int k)
	{
		ln(a,h,n);
//	for(int i=0;i<n;i++) write(h[i],' ');
//	write('\n');
		for(int i=0;i<n;i++) h[i]=1ll*h[i]*k%mod;
		exp(h,b,n);
	}
	void pow(int *a,int *b,int n,int k1,int k2)
	{
		ll del=0;
		while(del<n&&!a[del]) del++;
		if((ll)del*k1>=n)
		{
			for(int i=0;i<n;i++) b[i]=0;
			return;
		}
		int inv1=qpow(a[del],mod-2),inv2=qpow(a[del],k2);
		for(int i=del;i<n;i++) a[i-del]=1ll*a[i]*inv1%mod;
		for(int i=n-del;i<n;i++) a[i]=0;
		__basic_pow(a,b,n,k1);
		del*=k1;
		for(int i=n-1;i>=del;i--) b[i]=1ll*b[i-del]*inv2%mod;
		for(int i=0;i<del&&i<n;i++) b[i]=0;
	}
}
int f[N],g[N],h[N];
//bool Med;
signed main()
{
//	cerr<<"Memory Size: "<<abs((&Med)-(&Mst))/1024.0/1024<<" MB\n";
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	POLY::init();
	int n;
	cin>>n;
	auto upd=[&](ll k,ll op)->void
	{
		ll co=pr(-k%mod)*op%mod;
		for(ll i=0;i+k-1<=n;i+=k) f[i+k-1]=rd(f[i+k-1]+co);
	};
	for(int i=1,x;i<=n;i++) cin>>x,upd(i,mod-1),upd(1ll*(x+1)*i,1);
	POLY::intg(f,g,n+2),POLY::exp(g,h,n+2);
//	for(int i=0;i<=n;i++) cout<<f[i]<<" ";
//	cout<<'\n';
//	for(int i=0;i<=n;i++) cout<<g[i]<<" ";
//	cout<<'\n';
//	for(int i=0;i<=n;i++) cout<<h[i]<<" ";
//	cout<<'\n';
	cout<<h[n]<<"\n";
	return 0;
}

Submission Info

Judge Result