51nod 1556 計算

默慈金數的應用

在一個“網格”上，若限定“每步隻能向右移動一格(可以向右上、右下橫向向右)，并禁止移動到y=0以下的地方”，則以這種走法用n步從(0,0)移動至(n,0)的可能形成的路徑的總數為n的默慈金數。

初始狀态：

M[0]=1

M[1]=1

M[2]=2

遞推公式：

M[n+1]=((2n+3)*M[n]+3n*M[n-1])/(n+3)

直接計算比較困難，可以計算出全部種數3^(n-1)，再減去錯誤走法

利用默慈金數，可以計算出(1,1)走到(1,x)的合法走法的種數。假設下一步往下走，那麼不論之後再怎麼走，肯定是錯誤走法。周遊x的所有情況，減去錯誤走法，即可得到答案。

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

const long long mod=1e9+7;
const int MAXN=1000100;
long long m[MAXN];

long long powmod(long long x,long long p)
{
	long long ret=1;
	while(p)
	{
		if(p&1)
			ret=ret*x%mod;
		x=x*x%mod;
		p>>=1;
	}
	return ret;
}

int main()
{
	long long i,n,ans;
	while(~scanf("%lld",&n))
	{
		m[0]=1;	m[1]=1;	m[2]=2;
		for(i=2;i<n;i++)
		{
			m[i+1]=((2*i+3)*m[i]+3*i*m[i-1])%mod*powmod(i+3,mod-2)%mod;
		}
		ans=powmod(3,n-1);
		for(i=1;i<n;i++)
		{
			ans=((ans-m[i-1]*powmod(3,n-i-1)%mod)%mod+mod)%mod;
		}
		printf("%lld\n",ans);
	}
}