ARC118F Growth Rate

给出个长度为(n)的序列(A_i)，问有多少个长度为(n+1)的序列(X_i)，满足：

(X_iin [1,m])。
(A_iX_ile X_{i+1})

(nle 1000,mle 10^{18}，prod A_ile M)

首先有个暴力：从后往前做，设(f_k(x))表示第(k)位选择(x)的方案数是什么。

转移：(f_k(x)=sum_{yge ax} f_{k+1}(y))

结论：(f_k(x))是个关于(x)的多项式，定义域为([1,R])，(R)为原题意中于(k)位置能合法放置的最大数。原因根据以下做法，归纳就能说明。

假设已经知道了(f_k(y)=sum_i a_i y^i)。

令(F_k(x))表示(f_k(x))的前缀和，即(F_{k}(x)=sum_{yle x} f_k(y)=sum_i a_i sum_{yle x}y^i)，后面是个自然数幂和，所以(F_k(x))也是多项式。

根据转移，(f_{k+1}(x)=F_k(R)-F_k(ax-1))。显然(f_{k+1}(x))也是多项式。

现在问题是两个：给多项式做前缀和；给多项式复合(ax-1)。

先讲题解做法：

考虑维护若干个点值（假设(c)个，(c=O(n))），分别为(1,2,dots c)。

前缀和：直接用点值前缀和。时间(O(n))。

复合：对于每个点(x_i)，通过拉格朗日插值查(F_k(ax_i-1))。时间(O(n^2))。

在(A_k>1)时直接(O(n^2))复合，次数(O(lg m))次；(A_k=1)时特殊处理：前缀和就直接前缀和，后面是(F_k(R)-F_k(x-1))，(F_k(x-1))已知可以直接用。于是时间(O(n))。

于是总时间(O(n^2lg m))。

我的口胡做法：

考虑对前缀和进行一波多项式推导（以下(B)为伯努利数(B^+)）：

[sum_i a_i sum_{yle x}y^i\ =sum_i a_i frac{1}{i+1}sum_{j=1}^{i+1}inom{i+1}{j}B_{i+1-j}x^{j}\ =sum_{jge 1}x^{j}sum_{i+1ge j}a_i frac{1}{i+1}inom{i+1}{j}B_{i+1-j}\ =sum_{jge 1}frac{x^{j}}{j!}sum_{i+1ge j}(a_ii!) frac{B_{i+1-j}}{(i+1-j)!}\ ]

可以发现最后是个减法卷积的形式。

再对复合进行一波多项式推导：

[F(ax-1)\ =sum_i F_i(ax-1)^i\ =sum_i F_isum_{j=0}^ia^jx^j(-1)^{i-j}inom{i}{j}\ =sum_{j}a^jx^j(-1)^{j}sum_{ige j} F_iinom{i}{j}(-1)^i\ =sum_{j}a^jx^jfrac{(-1)^{j}}{j!}sum_{ige j} left(F_ii!(-1)^i ight)left(frac{1}{(i-j)!} ight) ]

也是个减法卷积的形式。

于是全程用多项式做，可以搞到(O(n^2 lg n))的复杂度。

using namespace std;
#include <bits/stdc++.h>
#define N 1005
#define ll long long
#define mo 998244353
ll qpow(ll x,ll y=mo-2){
	ll r=1;
	for (;y;y>>=1,x=x*x%mo)
		if (y&1)
			r=r*x%mo;
	return r;
}
int n,k;
ll m,a[N];
ll d[N],R;
ll fac[N],ifac[N];
void initC(int n){
	fac[0]=1;
	for (int i=1;i<=n;++i)
		fac[i]=fac[i-1]*i%mo;
	ifac[n]=qpow(fac[n]);
	for (int i=n-1;i>=0;--i)
		ifac[i]=ifac[i+1]*(i+1)%mo;
}
ll ask(ll z){
	if (z>R || z<1) return 0;
	z%=mo;
	ll y=0,pre=1;
	static ll suc[N];
	suc[k+1]=1;
	for (int x=k;x>=1;--x)
		suc[x]=suc[x+1]*(z-x)%mo;
	for (int x=1;x<=k;++x){
		ll tmp=pre*suc[x+1]%mo;
		(y+=d[x]*tmp%mo*ifac[k-x]%mo*ifac[x-1]*(k-x&1?-1:1))%=mo;
		pre=pre*(z-x)%mo;
	}
	return (y+mo)%mo;
}
ll C(ll m,ll n){
	ll s=1;
	for (ll i=m-n+1;i<=m;++i)
		s=s*i%mo;
	for (ll i=1;i<=n;++i)
		s=s*qpow(i)%mo;
	return s;
}
int main(){
	//freopen("in.txt","r",stdin);
	scanf("%d%lld",&n,&m);
	for (int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	k=n+2;
	initC(k);
	R=m;
	for (int x=1;x<=k;++x)
		d[x]=min((ll)x,m);
	m%=mo;
	for (int i=n;i>=1;--i){
		ll sum=ask(R);
		if (a[i]==1){
			for (int x=k;x>=1;--x)
				d[x]=(sum-d[x-1]+mo)%mo;
		}
		else{
			static ll t[N];
			for (int x=k;x>=1;--x)
				t[x]=(sum-ask(a[i]*x-1)+mo)%mo;
			memcpy(d,t,sizeof(ll)*(k+1));			
		}
		R=R/a[i];
		for (int x=1;x<=k;++x)
			d[x]=(d[x]+d[x-1]+mo)%mo;
	}
	ll ans=ask(R);
	printf("%lld
",ans);
	return 0;
}