51nod 1556 计算(递推)

传送门

解题思路

　　在一个网格图上走(n)步，每次可以向右上，右下，右，但必须在第一象限，最后从((0,0))走到((n,0))的方案数为默慈金数。递推式为(m[i+1]=frac{(2*i+3)*m[i]+3*i*m[i-1]}{n+3})。然后原题中如果在(x)轴上就只有两种方案，其余有(3)种方案，所以递推式为(f[i]=f[i-1]*3-m[i-1])。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>

using namespace std;
const int MAXN = 1000005;
const int MOD = 1e9+7;
typedef long long LL;

int n,m[MAXN],f[MAXN];

int fast_pow(int x,int y){
	int ret=1;
	for(;y;y>>=1){
		if(y&1) ret=(LL)ret*x%MOD;
		x=(LL)x*x%MOD;		
	}
	return ret;
}

int main(){
	scanf("%d",&n);m[1]=1;m[2]=2;f[1]=2;
	for(int i=3;i<n;i++) m[i]=(LL)((LL)(2*i+1)*m[i-1]%MOD+(LL)3*(i-1)*m[i-2]%MOD)%MOD*fast_pow(i+2,MOD-2)%MOD;
	for(int i=2;i<n;i++) f[i]=((LL)f[i-1]*3-m[i-1]+MOD)%MOD;
	printf("%d
",f[n-1]);
	return 0;	
}