2019 Sichuan Province Programming Contest J. Jump on Axis

题目链接：https://codeforces.com/gym/102821/problem/J

题意：给你一个坐标k，每次从0开始走

每次有三个选择：选择1走一步，选择2走两步，选择3走三步

每次选第i个选择的时候，如果他没有被选过，那么就走i步

如果他被选过了的话就走上一次选择这个选择走过的步数+3步

问：到k的最小步数和到k有多少种方法

思路：我们把每次选择打表：

 然后我们可以用一个二维数组v【i】【j】来预处理存选项i一共选了j次所走的路程

设选项1走了i次，选项2走了j次，选项3走了k次

我们只用列举一下i和j的路程，然后算出k

如果满足条件更新步数ans=min(ans,i+j+k)

然后对于每个满足的i j k，选择的方案是C（i+j+k，i）*C（j+k，j）

（在i+j+k个位置里选i个位置走选项1，在剩下的j+k个位置走选项2）

然后我们化简一下就是：

因为需要取模，然后我们就要用逆元求一下阶乘的倒数r【i！】数组，还需要求一下阶乘f【i】数组 

由打表可以知道i，j，k不超过2600个，

而且最后是i+j+k，那么我们就开3*3000个数组

具体代码如下：

#include<bits/stdc++.h>
using namespace std;
#define int long long 
typedef long long ll;
int n,ans,con;
const int N=3*3000,mod=1e9+7;
int f[N],r[N];
vector<int> v[5];
int ksm(int a,int b,int p){
	int res=1%p;
	while(b){
		if(b&1)res=res*a%p;
		a=a*a%p;
		b>>=1;
	}
	return res;
}
void init(){
	for(int i=1;i<=3;i++){//预处理选项i选了j次走的路程
		v[i].push_back(0);//当选0次的时候走了0
		for(int j=1;;j++){
			int op=v[i][j-1]+(j-1)*3+i;
			if(op>1e7)break;//当大于1e7的时候剪枝
			v[i].push_back(op); 
		} 
		v[i].push_back(1e9); //最后加上个大整数是方便lower_bound查找
	}
	f[0]=r[0]=1;
	for(int i=1;i<N;i++){//处理阶乘
		f[i]=f[i-1]*i%mod;
	}
	for(int i=1;i<N;i++){//处理阶乘的逆元
		r[i]=ksm(f[i],mod-2,mod);
	}
}
signed main(){
	init();
	int t;
	scanf("%lld",&t);
	for(int p=1;p<=t;p++){
		ans=1e9;
		cin>>n;
		con=0;
		for(int i=0;v[1][i]<=n;i++){//列举选项1
			for(int j=0;v[1][i]+v[2][j]<=n;j++){//列举选项2
				int x=n-v[1][i]-v[2][j];//算选项3
				int k=lower_bound(v[3].begin() ,v[3].end() ,x )-v[3].begin() ;
				if(v[3][k]==x){//如果满足
					ans=min(ans,i+j+k);
					con=(con+f[i+j+k]*r[i]%mod*r[j]%mod*r[k]%mod)%mod;
				}
			}
		}
		printf("Case %lld: %lld %lld\n",p,ans,con);
	}
	return 0;
}