AtCoder ARC #118 : F - Growth Rate

シンプルな問題設定。
https://atcoder.jp/contests/arc118/tasks/arc118_f

問題

正整数Mと、N要素の正整数列Aが与えられる。
以下の条件を満たす、N+1要素の正整数列Xは何通りか。

• X[i]は1以上M以下
• A[i]*X[i]≦X[i+1]

解法

Y[i]を、X[i]の取りうる最大値、すなわち

• Y[N]=M
• Y[i]=floor(Y[i+1]/A[i])

とする。

f(n,x) := X[n]=xで、X[n+1]以降が条件を満たすようなX[n]以降の値の組み合わせ
g(n,x) := f(n,x)の累積和(f(n,1)+....+f(n,x)
とする。f(n,x)は(N+1-n)次の関数、g(n,x)は(N+2-n)次の関数となる。

よって、g(1,0)～g(1,N+2)がわかれば、ラグランジュ補間でg(1,Y[0])、すなわち解を求めることができる。
f,gは多項式の係数ではなく、こちらも適宜ラグランジュ補間できるように、n次の多項式となるならx=0～(n+1)に対応する値を持つようにしよう。

f(N,x)=1、g(N,x)=xから初めて、後ろからf,gを求めて行こう。
f(n,x) = g(n+1,Y[n+1])-g(n+1,A[n+1]*x-1)
なので、g(n+1,x)がわかればf(n,x)を求めることができる。このg(n+1,x)自体もラグランジュ補間で求めよう。

int N;
ll M;
ll A[101010];
const ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll lagrange(vector<ll>& P,ll x) {
	const int NUM_=2000003;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}

	int i;
	int N=P.size();
	if(0<=x&&x<N) return P[x];
	vector<ll> R={1},F={1};
	for(i=N-1;i>=1;i--) R.push_back(R.back()*((x-i)%mo)%mo);
	
	ll p=1;
	ll ret=0;
	FOR(i,N) {
		ll a=p*R.back()%mo*factr[i]%mo;
		if((N-1-i)%2==0) a=a*factr[N-1-i]%mo;
		else a=a*(mo-factr[N-1-i])%mo;
		(ret+=a*P[i])%=mo;
		R.pop_back();
		(p*=(x-i)%mo)%=mo;
	}
	return ret%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	
	vector<ll> F={0,1};
	ll R=M;
	for(x=N-1;x>=0;x--) {
		ll TR=R/A[x];
		if(TR<=0) {
			cout<<0<<endl;
			return;
		}
		ll sum=lagrange(F,R);
		int S=F.size();
		vector<ll> F2(S+1);
		for(i=1;i<=S;i++) F2[i]=(sum+mo-lagrange(F,A[x]*i-1))%mo;
		
		F=F2;
		for(i=1;i<=S;i++) (F[i]+=F[i-1])%=mo;
		R=TR;
	}
	
	
	cout<<lagrange(F,R)<<endl;
	
}

まとめ

ラグランジュ補間久しぶりだな。