题目链接：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
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 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次的时候走了0for(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;con=0;for(int i=0;v[1][i]<=n;i++){//列举选项1for(int j=0;v[1][i]+v[2][j]<=n;j++){//列举选项2int x=n-v[1][i]-v[2][j];//算选项3int 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;
}