Railgun

Railgun

题意

给定 $n,a,b$，你现在在 $0$ 处跳格子，每次可以向前跳 $a$ 格或者 $b$ 格。

求到达 $n$ 格的方案数，答案对 $10,007$ 取模。$(n,a,b\in[1,10^9])$

Sol

令 $b\leq a$，考虑暴力递推式

$f_i = f_{i-a} + f_{i-b} \tag{i $\geq$ a, i $\geq$ b}$

那么我们可以通过矩阵乘法快速幂加速递推，时间复杂度为 $\text{O}(a^3\log { n } )$。

然而在 $a\geq 500$ 左右会 TLE，此时考虑另外一种处理方案。

令 $a\cdot x+b\cdot y = n$，那么当我们枚举得到非负整数 $x,y$ 的取值时，只需要考虑跳 $a,b$ 格的操作顺序即可得到贡献，单次贡献为 $\dbinom{x+y}{x}$，考虑到模数较小，我们使用卢卡斯定理计算组合数。由于 $a\geq 100$ 时，枚举的 $x,y$ 取值上界为 $\frac{n}{a}=\frac{10^9}{100}=10^7$ 左右，在时限可以接受的范围之内。

那么我们对于 $a\leq 100$ 和 $a\geq 100$ 时进行数据分治即可。

#include<bits/stdc++.h>
using namespace std;

template <typename T>
inline T read(){
	T x=0,f=1;char c=getchar();
	while(!isdigit(c)){	if(c=='-') f=-f;c=getchar();}
	while(isdigit(c)){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}

#define lint long long int
#define ulint unsigned lint
#define readint read<int>()
#define readlint read<lint>()
const int inf=1e9+1e7,Mod=1e4+7;
const lint INF=1e18+1e9;

int n,m,a,b;

lint Abs(lint x){
	return (x<0 ? (x%Mod+Mod)%Mod : x%Mod);
}

namespace Subtask1{// f { i } = f { i - a } + f { i - b }

const int MAXN=2e2+1e1;

struct Matrix{
	lint a[MAXN][MAXN],r;

	void Clear(){
		for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=0;
		return;
	}

	void Init(){
		for(int i=1;i<=n;i++) a[i][i]=1;
		return;
	}

	friend Matrix operator *(const Matrix &A, const Matrix &B){
		Matrix res;res.Clear(),res.r=A.r;
		for(int i=1;i<=A.r;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++){
			res.a[i][j]=Abs(res.a[i][j]+Abs(A.a[i][k]*B.a[k][j]));
		}
		return res;
	}

	friend Matrix operator ^(const Matrix &A, const int &B){
		Matrix res,tmpA=A;res.Clear(),res.Init(),res.r=n;
		int tmpB=B;
		while(tmpB>0){
			if(tmpB&1) res=res*tmpA;
			tmpA=tmpA*tmpA,tmpB>>=1;
		}
		return res;
	}
}M,Ans;

void Solve(){
	n=max(a,b),M.Clear(),Ans.Clear();
	Ans.r=Ans.a[1][0]=M.a[n-a+1][n]=M.a[n-b+1][n]=1,M.r=n;
	for(int i=2;i<=n;i++) M.a[i][i-1]=1;
	for(int i=1;i<=n;i++){
		if(i>=a) Ans.a[1][i]=Abs(Ans.a[1][i]+Ans.a[1][i-a]);
		if(i>=b) Ans.a[1][i]=Abs(Ans.a[1][i]+Ans.a[1][i-b]);
	}
	Ans=Ans*(M^(m-1));
	printf("%lld\n",Ans.a[1][1]);
	return;
}

}

namespace Subtask2{// a * x + b * y = n

const int MAXN=1e7+1e1;

lint fac[MAXN],inv[MAXN],Ans;

lint Qpow(lint A,int B){
	lint res=1;
	while(B>0){
		if(B&1) res=Abs(res*A);
		A=Abs(A*A),B>>=1;
	}
	return res;
}

lint C(int A,int B){
	if(A<Mod && B<Mod){
		if(A<0 || B<0 || A<B) return 0;
		return Abs(fac[A]*Abs(inv[B]*inv[A-B]));
	}
	return Abs(C(A%Mod,B%Mod)*C(A/Mod,B/Mod));
}

void Solve(){
	if(a<b) swap(a,b);
	fac[0]=inv[0]=1;
	for(int i=1;i<Mod;i++) fac[i]=Abs(fac[i-1]*i);
	inv[Mod-1]=Qpow(fac[Mod-1],Mod-2);
	for(int i=Mod-1;i;i--) inv[i-1]=Abs(inv[i]*i);
	for(int i=0;i<=(m/a);i++) if(!((m-a*i)%b)){
		Ans=Abs(Ans+C(i+(m-a*i)/b,i));
	}
	printf("%lld\n",Ans);
	return;
}

}

int main(void){

	scanf("%d%d%d",&m,&a,&b);
	if(max(a,b)<=100) Subtask1::Solve();
	else Subtask2::Solve();

	return 0;
}